99eae0945db4559ffa0d63aebd9517ea2dfacf73
[WebKit-https.git] / Source / WTF / wtf / text / StringImpl.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller ( mueller@kde.org )
5  * Copyright (C) 2003-2017 Apple Inc. All rights reserved.
6  * Copyright (C) 2006 Andrew Wellington (proton@wiretapped.net)
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  *
23  */
24
25 #include "config.h"
26 #include "StringImpl.h"
27
28 #include "AtomicString.h"
29 #include "StringBuffer.h"
30 #include "StringHash.h"
31 #include <wtf/Gigacage.h>
32 #include <wtf/ProcessID.h>
33 #include <wtf/StdLibExtras.h>
34 #include <wtf/text/CString.h>
35 #include <wtf/text/StringMalloc.h>
36 #include <wtf/text/StringView.h>
37 #include <wtf/text/SymbolImpl.h>
38 #include <wtf/text/SymbolRegistry.h>
39 #include <wtf/unicode/CharacterNames.h>
40 #include <wtf/unicode/UTF8.h>
41
42 #if STRING_STATS
43 #include <unistd.h>
44 #include <wtf/DataLog.h>
45 #endif
46
47 namespace WTF {
48
49 using namespace Unicode;
50
51 static_assert(sizeof(StringImpl) == 2 * sizeof(int) + 2 * sizeof(void*), "StringImpl should stay small");
52
53 #if STRING_STATS
54 StringStats StringImpl::m_stringStats;
55
56 std::atomic<unsigned> StringStats::s_stringRemovesTillPrintStats(s_printStringStatsFrequency);
57
58 void StringStats::removeString(StringImpl& string)
59 {
60     unsigned length = string.length();
61     bool isSubString = string.isSubString();
62
63     --m_totalNumberStrings;
64
65     if (string.is8Bit()) {
66         --m_number8BitStrings;
67         if (!isSubString)
68             m_total8BitData -= length;
69     } else {
70         --m_number16BitStrings;
71         if (!isSubString)
72             m_total16BitData -= length;
73     }
74
75     if (!--s_stringRemovesTillPrintStats) {
76         s_stringRemovesTillPrintStats = s_printStringStatsFrequency;
77         printStats();
78     }
79 }
80
81 void StringStats::printStats()
82 {
83     dataLogF("String stats for process id %d:\n", getCurrentProcessID());
84
85     unsigned long long totalNumberCharacters = m_total8BitData + m_total16BitData;
86     double percent8Bit = m_totalNumberStrings ? ((double)m_number8BitStrings * 100) / (double)m_totalNumberStrings : 0.0;
87     double average8bitLength = m_number8BitStrings ? (double)m_total8BitData / (double)m_number8BitStrings : 0.0;
88     dataLogF("%8u (%5.2f%%) 8 bit        %12llu chars  %12llu bytes  avg length %6.1f\n", m_number8BitStrings.load(), percent8Bit, m_total8BitData.load(), m_total8BitData.load(), average8bitLength);
89
90     double percent16Bit = m_totalNumberStrings ? ((double)m_number16BitStrings * 100) / (double)m_totalNumberStrings : 0.0;
91     double average16bitLength = m_number16BitStrings ? (double)m_total16BitData / (double)m_number16BitStrings : 0.0;
92     dataLogF("%8u (%5.2f%%) 16 bit       %12llu chars  %12llu bytes  avg length %6.1f\n", m_number16BitStrings.load(), percent16Bit, m_total16BitData.load(), m_total16BitData * 2, average16bitLength);
93
94     double averageLength = m_totalNumberStrings ? (double)totalNumberCharacters / (double)m_totalNumberStrings : 0.0;
95     unsigned long long totalDataBytes = m_total8BitData + m_total16BitData * 2;
96     dataLogF("%8u Total                 %12llu chars  %12llu bytes  avg length %6.1f\n", m_totalNumberStrings.load(), totalNumberCharacters, totalDataBytes, averageLength);
97     unsigned long long totalSavedBytes = m_total8BitData;
98     double percentSavings = totalSavedBytes ? ((double)totalSavedBytes * 100) / (double)(totalDataBytes + totalSavedBytes) : 0.0;
99     dataLogF("         Total savings %12llu bytes (%5.2f%%)\n", totalSavedBytes, percentSavings);
100
101     dataLogF("%8u StringImpl::ref calls\n", m_refCalls.load());
102     dataLogF("%8u StringImpl::deref calls\n", m_derefCalls.load());
103 }
104 #endif
105
106 StringImpl::StaticStringImpl StringImpl::s_atomicEmptyString("", StringImpl::StringAtomic);
107
108 StringImpl::~StringImpl()
109 {
110     ASSERT(!isStatic());
111
112     StringView::invalidate(*this);
113
114     STRING_STATS_REMOVE_STRING(*this);
115
116     if (isAtomic()) {
117         ASSERT(!isSymbol());
118         if (length())
119             AtomicStringImpl::remove(static_cast<AtomicStringImpl*>(this));
120     } else if (isSymbol()) {
121         auto& symbol = static_cast<SymbolImpl&>(*this);
122         auto* symbolRegistry = symbol.symbolRegistry();
123         if (symbolRegistry)
124             symbolRegistry->remove(*symbol.asRegisteredSymbolImpl());
125     }
126
127     BufferOwnership ownership = bufferOwnership();
128
129     if (ownership == BufferInternal)
130         return;
131     if (ownership == BufferOwned) {
132         // We use m_data8, but since it is a union with m_data16 this works either way.
133         ASSERT(m_data8);
134         stringFree(const_cast<LChar*>(m_data8));
135         return;
136     }
137
138     ASSERT(ownership == BufferSubstring);
139     ASSERT(substringBuffer());
140     substringBuffer()->deref();
141 }
142
143 void StringImpl::destroy(StringImpl* stringImpl)
144 {
145     stringImpl->~StringImpl();
146     stringFree(stringImpl);
147 }
148
149 Ref<StringImpl> StringImpl::createFromLiteral(const char* characters, unsigned length)
150 {
151     ASSERT_WITH_MESSAGE(length, "Use StringImpl::empty() to create an empty string");
152     ASSERT(charactersAreAllASCII<LChar>(reinterpret_cast<const LChar*>(characters), length));
153     return adoptRef(*new StringImpl(reinterpret_cast<const LChar*>(characters), length, ConstructWithoutCopying));
154 }
155
156 Ref<StringImpl> StringImpl::createFromLiteral(const char* characters)
157 {
158     return createFromLiteral(characters, strlen(characters));
159 }
160
161 Ref<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, unsigned length)
162 {
163     if (!length)
164         return *empty();
165     return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));
166 }
167
168 Ref<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, unsigned length)
169 {
170     if (!length)
171         return *empty();
172     return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));
173 }
174
175 template<typename CharacterType> inline Ref<StringImpl> StringImpl::createUninitializedInternal(unsigned length, CharacterType*& data)
176 {
177     if (!length) {
178         data = 0;
179         return *empty();
180     }
181     return createUninitializedInternalNonEmpty(length, data);
182 }
183
184 template<typename CharacterType> inline Ref<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsigned length, CharacterType*& data)
185 {
186     ASSERT(length);
187
188     // Allocate a single buffer large enough to contain the StringImpl
189     // struct as well as the data which it contains. This removes one
190     // heap allocation from this call.
191     if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))
192         CRASH();
193     StringImpl* string = static_cast<StringImpl*>(stringMalloc(allocationSize<CharacterType>(length)));
194
195     data = string->tailPointer<CharacterType>();
196     return constructInternal<CharacterType>(*string, length);
197 }
198
199 Ref<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data)
200 {
201     return createUninitializedInternal(length, data);
202 }
203
204 Ref<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data)
205 {
206     return createUninitializedInternal(length, data);
207 }
208
209 template<typename CharacterType> inline Ref<StringImpl> StringImpl::reallocateInternal(Ref<StringImpl>&& originalString, unsigned length, CharacterType*& data)
210 {
211     ASSERT(originalString->hasOneRef());
212     ASSERT(originalString->bufferOwnership() == BufferInternal);
213
214     if (!length) {
215         data = 0;
216         return *empty();
217     }
218
219     // Same as createUninitialized() except here we use stringRealloc.
220     if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))
221         CRASH();
222
223     originalString->~StringImpl();
224     auto* string = static_cast<StringImpl*>(stringRealloc(&originalString.leakRef(), allocationSize<CharacterType>(length)));
225
226     data = string->tailPointer<CharacterType>();
227     return constructInternal<CharacterType>(*string, length);
228 }
229
230 Ref<StringImpl> StringImpl::reallocate(Ref<StringImpl>&& originalString, unsigned length, LChar*& data)
231 {
232     ASSERT(originalString->is8Bit());
233     return reallocateInternal(WTFMove(originalString), length, data);
234 }
235
236 Ref<StringImpl> StringImpl::reallocate(Ref<StringImpl>&& originalString, unsigned length, UChar*& data)
237 {
238     ASSERT(!originalString->is8Bit());
239     return reallocateInternal(WTFMove(originalString), length, data);
240 }
241
242 template<typename CharacterType> inline Ref<StringImpl> StringImpl::createInternal(const CharacterType* characters, unsigned length)
243 {
244     if (!characters || !length)
245         return *empty();
246     CharacterType* data;
247     auto string = createUninitializedInternalNonEmpty(length, data);
248     copyCharacters(data, characters, length);
249     return string;
250 }
251
252 Ref<StringImpl> StringImpl::create(const UChar* characters, unsigned length)
253 {
254     return createInternal(characters, length);
255 }
256
257 Ref<StringImpl> StringImpl::create(const LChar* characters, unsigned length)
258 {
259     return createInternal(characters, length);
260 }
261
262 Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length)
263 {
264     if (!characters || !length)
265         return *empty();
266
267     LChar* data;
268     auto string = createUninitializedInternalNonEmpty(length, data);
269
270     for (size_t i = 0; i < length; ++i) {
271         if (characters[i] & 0xFF00)
272             return create(characters, length);
273         data[i] = static_cast<LChar>(characters[i]);
274     }
275
276     return string;
277 }
278
279 Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* string)
280 {
281     return StringImpl::create8BitIfPossible(string, lengthOfNullTerminatedString(string));
282 }
283
284 Ref<StringImpl> StringImpl::create(const LChar* string)
285 {
286     if (!string)
287         return *empty();
288     size_t length = strlen(reinterpret_cast<const char*>(string));
289     if (length > std::numeric_limits<unsigned>::max())
290         CRASH();
291     return create(string, length);
292 }
293
294 Ref<StringImpl> StringImpl::substring(unsigned start, unsigned length)
295 {
296     if (start >= m_length)
297         return *empty();
298     unsigned maxLength = m_length - start;
299     if (length >= maxLength) {
300         if (!start)
301             return *this;
302         length = maxLength;
303     }
304     if (is8Bit())
305         return create(m_data8 + start, length);
306
307     return create(m_data16 + start, length);
308 }
309
310 UChar32 StringImpl::characterStartingAt(unsigned i)
311 {
312     if (is8Bit())
313         return m_data8[i];
314     if (U16_IS_SINGLE(m_data16[i]))
315         return m_data16[i];
316     if (i + 1 < m_length && U16_IS_LEAD(m_data16[i]) && U16_IS_TRAIL(m_data16[i + 1]))
317         return U16_GET_SUPPLEMENTARY(m_data16[i], m_data16[i + 1]);
318     return 0;
319 }
320
321 Ref<StringImpl> StringImpl::convertToLowercaseWithoutLocale()
322 {
323     // Note: At one time this was a hot function in the Dromaeo benchmark, specifically the
324     // no-op code path that may return ourself if we find no upper case letters and no invalid
325     // ASCII letters.
326
327     // First scan the string for uppercase and non-ASCII characters:
328     if (is8Bit()) {
329         for (unsigned i = 0; i < m_length; ++i) {
330             LChar character = m_data8[i];
331             if (UNLIKELY((character & ~0x7F) || isASCIIUpper(character)))
332                 return convertToLowercaseWithoutLocaleStartingAtFailingIndex8Bit(i);
333         }
334
335         return *this;
336     }
337
338     bool noUpper = true;
339     unsigned ored = 0;
340
341     for (unsigned i = 0; i < m_length; ++i) {
342         UChar character = m_data16[i];
343         if (UNLIKELY(isASCIIUpper(character)))
344             noUpper = false;
345         ored |= character;
346     }
347     // Nothing to do if the string is all ASCII with no uppercase.
348     if (noUpper && !(ored & ~0x7F))
349         return *this;
350
351     if (!(ored & ~0x7F)) {
352         UChar* data16;
353         auto newImpl = createUninitializedInternalNonEmpty(m_length, data16);
354         for (unsigned i = 0; i < m_length; ++i)
355             data16[i] = toASCIILower(m_data16[i]);
356         return newImpl;
357     }
358
359     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
360         CRASH();
361     int32_t length = m_length;
362
363     // Do a slower implementation for cases that include non-ASCII characters.
364     UChar* data16;
365     auto newImpl = createUninitializedInternalNonEmpty(m_length, data16);
366
367     UErrorCode status = U_ZERO_ERROR;
368     int32_t realLength = u_strToLower(data16, length, m_data16, m_length, "", &status);
369     if (U_SUCCESS(status) && realLength == length)
370         return newImpl;
371
372     newImpl = createUninitialized(realLength, data16);
373     status = U_ZERO_ERROR;
374     u_strToLower(data16, realLength, m_data16, m_length, "", &status);
375     if (U_FAILURE(status))
376         return *this;
377     return newImpl;
378 }
379
380 Ref<StringImpl> StringImpl::convertToLowercaseWithoutLocaleStartingAtFailingIndex8Bit(unsigned failingIndex)
381 {
382     ASSERT(is8Bit());
383     LChar* data8;
384     auto newImpl = createUninitializedInternalNonEmpty(m_length, data8);
385
386     for (unsigned i = 0; i < failingIndex; ++i) {
387         ASSERT(!(m_data8[i] & ~0x7F) && !isASCIIUpper(m_data8[i]));
388         data8[i] = m_data8[i];
389     }
390
391     for (unsigned i = failingIndex; i < m_length; ++i) {
392         LChar character = m_data8[i];
393         if (!(character & ~0x7F))
394             data8[i] = toASCIILower(character);
395         else {
396             ASSERT(u_tolower(character) <= 0xFF);
397             data8[i] = static_cast<LChar>(u_tolower(character));
398         }
399     }
400
401     return newImpl;
402 }
403
404 Ref<StringImpl> StringImpl::convertToUppercaseWithoutLocale()
405 {
406     // This function could be optimized for no-op cases the way
407     // convertToLowercaseWithoutLocale() is, but in empirical testing,
408     // few actual calls to upper() are no-ops, so it wouldn't be worth
409     // the extra time for pre-scanning.
410
411     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
412         CRASH();
413     int32_t length = m_length;
414
415     if (is8Bit()) {
416         LChar* data8;
417         auto newImpl = createUninitialized(m_length, data8);
418         
419         // Do a faster loop for the case where all the characters are ASCII.
420         unsigned ored = 0;
421         for (int i = 0; i < length; ++i) {
422             LChar character = m_data8[i];
423             ored |= character;
424             data8[i] = toASCIIUpper(character);
425         }
426         if (!(ored & ~0x7F))
427             return newImpl;
428
429         // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
430         int numberSharpSCharacters = 0;
431
432         // There are two special cases.
433         //  1. Some Latin-1 characters when converted to upper case are 16 bit characters.
434         //  2. Lower case sharp-S converts to "SS" (two characters)
435         for (int32_t i = 0; i < length; ++i) {
436             LChar character = m_data8[i];
437             if (UNLIKELY(character == smallLetterSharpS))
438                 ++numberSharpSCharacters;
439             ASSERT(u_toupper(character) <= 0xFFFF);
440             UChar upper = u_toupper(character);
441             if (UNLIKELY(upper > 0xFF)) {
442                 // Since this upper-cased character does not fit in an 8-bit string, we need to take the 16-bit path.
443                 goto upconvert;
444             }
445             data8[i] = static_cast<LChar>(upper);
446         }
447
448         if (!numberSharpSCharacters)
449             return newImpl;
450
451         // We have numberSSCharacters sharp-s characters, but none of the other special characters.
452         newImpl = createUninitialized(m_length + numberSharpSCharacters, data8);
453
454         LChar* dest = data8;
455
456         for (int32_t i = 0; i < length; ++i) {
457             LChar character = m_data8[i];
458             if (character == smallLetterSharpS) {
459                 *dest++ = 'S';
460                 *dest++ = 'S';
461             } else {
462                 ASSERT(u_toupper(character) <= 0xFF);
463                 *dest++ = static_cast<LChar>(u_toupper(character));
464             }
465         }
466
467         return newImpl;
468     }
469
470 upconvert:
471     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
472     const UChar* source16 = upconvertedCharacters;
473
474     UChar* data16;
475     auto newImpl = createUninitialized(m_length, data16);
476     
477     // Do a faster loop for the case where all the characters are ASCII.
478     unsigned ored = 0;
479     for (int i = 0; i < length; ++i) {
480         UChar character = source16[i];
481         ored |= character;
482         data16[i] = toASCIIUpper(character);
483     }
484     if (!(ored & ~0x7F))
485         return newImpl;
486
487     // Do a slower implementation for cases that include non-ASCII characters.
488     UErrorCode status = U_ZERO_ERROR;
489     int32_t realLength = u_strToUpper(data16, length, source16, m_length, "", &status);
490     if (U_SUCCESS(status) && realLength == length)
491         return newImpl;
492     newImpl = createUninitialized(realLength, data16);
493     status = U_ZERO_ERROR;
494     u_strToUpper(data16, realLength, source16, m_length, "", &status);
495     if (U_FAILURE(status))
496         return *this;
497     return newImpl;
498 }
499
500 static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier)
501 {
502     // Either "tr" or "az" locale, with case sensitive comparison and allowing for an ignored subtag.
503     UChar first = localeIdentifier[0];
504     UChar second = localeIdentifier[1];
505     return ((isASCIIAlphaCaselessEqual(first, 't') && isASCIIAlphaCaselessEqual(second, 'r'))
506         || (isASCIIAlphaCaselessEqual(first, 'a') && isASCIIAlphaCaselessEqual(second, 'z')))
507         && (localeIdentifier.length() == 2 || localeIdentifier[2] == '-');
508 }
509
510 Ref<StringImpl> StringImpl::convertToLowercaseWithLocale(const AtomicString& localeIdentifier)
511 {
512     // Use the more-optimized code path most of the time.
513     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules.
514     // FIXME: Could possibly optimize further by looking for the specific sequences
515     // that have locale-specific lowercasing. There are only three of them.
516     if (!needsTurkishCasingRules(localeIdentifier))
517         return convertToLowercaseWithoutLocale();
518
519     // FIXME: Could share more code with the main StringImpl::lower by factoring out
520     // this last part into a shared function that takes a locale string, since this is
521     // just like the end of that function.
522
523     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
524         CRASH();
525     int length = m_length;
526
527     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
528     // allocating memory just to turn localeIdentifier into a C string, and we assume
529     // there is no difference between the uppercasing for "tr" and "az" locales.
530     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
531     const UChar* source16 = upconvertedCharacters;
532     UChar* data16;
533     auto newString = createUninitialized(length, data16);
534     UErrorCode status = U_ZERO_ERROR;
535     int realLength = u_strToLower(data16, length, source16, length, "tr", &status);
536     if (U_SUCCESS(status) && realLength == length)
537         return newString;
538     newString = createUninitialized(realLength, data16);
539     status = U_ZERO_ERROR;
540     u_strToLower(data16, realLength, source16, length, "tr", &status);
541     if (U_FAILURE(status))
542         return *this;
543     return newString;
544 }
545
546 Ref<StringImpl> StringImpl::convertToUppercaseWithLocale(const AtomicString& localeIdentifier)
547 {
548     // Use the more-optimized code path most of the time.
549     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules,
550     // and that the only affected character is lowercase "i".
551     if (!needsTurkishCasingRules(localeIdentifier) || find('i') == notFound)
552         return convertToUppercaseWithoutLocale();
553
554     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
555         CRASH();
556     int length = m_length;
557
558     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
559     // allocating memory just to turn localeIdentifier into a C string, and we assume
560     // there is no difference between the uppercasing for "tr" and "az" locales.
561     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
562     const UChar* source16 = upconvertedCharacters;
563     UChar* data16;
564     auto newString = createUninitialized(length, data16);
565     UErrorCode status = U_ZERO_ERROR;
566     int realLength = u_strToUpper(data16, length, source16, length, "tr", &status);
567     if (U_SUCCESS(status) && realLength == length)
568         return newString;
569     newString = createUninitialized(realLength, data16);
570     status = U_ZERO_ERROR;
571     u_strToUpper(data16, realLength, source16, length, "tr", &status);
572     if (U_FAILURE(status))
573         return *this;
574     return newString;
575 }
576
577 Ref<StringImpl> StringImpl::foldCase()
578 {
579     if (is8Bit()) {
580         unsigned failingIndex;
581         for (unsigned i = 0; i < m_length; ++i) {
582             auto character = m_data8[i];
583             if (UNLIKELY(!isASCII(character) || isASCIIUpper(character))) {
584                 failingIndex = i;
585                 goto SlowPath;
586             }
587         }
588         // String was all ASCII and no uppercase, so just return as-is.
589         return *this;
590
591 SlowPath:
592         bool need16BitCharacters = false;
593         for (unsigned i = failingIndex; i < m_length; ++i) {
594             auto character = m_data8[i];
595             if (character == 0xB5 || character == 0xDF) {
596                 need16BitCharacters = true;
597                 break;
598             }
599         }
600
601         if (!need16BitCharacters) {
602             LChar* data8;
603             auto folded = createUninitializedInternalNonEmpty(m_length, data8);
604             copyCharacters(data8, m_data8, failingIndex);
605             for (unsigned i = failingIndex; i < m_length; ++i) {
606                 auto character = m_data8[i];
607                 if (isASCII(character))
608                     data8[i] = toASCIILower(character);
609                 else {
610                     ASSERT(u_foldCase(character, U_FOLD_CASE_DEFAULT) <= 0xFF);
611                     data8[i] = static_cast<LChar>(u_foldCase(character, U_FOLD_CASE_DEFAULT));
612                 }
613             }
614             return folded;
615         }
616     } else {
617         // FIXME: Unclear why we use goto in the 8-bit case, and a different approach in the 16-bit case.
618         bool noUpper = true;
619         unsigned ored = 0;
620         for (unsigned i = 0; i < m_length; ++i) {
621             UChar character = m_data16[i];
622             if (UNLIKELY(isASCIIUpper(character)))
623                 noUpper = false;
624             ored |= character;
625         }
626         if (!(ored & ~0x7F)) {
627             if (noUpper) {
628                 // String was all ASCII and no uppercase, so just return as-is.
629                 return *this;
630             }
631             UChar* data16;
632             auto folded = createUninitializedInternalNonEmpty(m_length, data16);
633             for (unsigned i = 0; i < m_length; ++i)
634                 data16[i] = toASCIILower(m_data16[i]);
635             return folded;
636         }
637     }
638
639     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
640         CRASH();
641
642     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
643
644     UChar* data;
645     auto folded = createUninitializedInternalNonEmpty(m_length, data);
646     int32_t length = m_length;
647     UErrorCode status = U_ZERO_ERROR;
648     int32_t realLength = u_strFoldCase(data, length, upconvertedCharacters, length, U_FOLD_CASE_DEFAULT, &status);
649     if (U_SUCCESS(status) && realLength == length)
650         return folded;
651     ASSERT(realLength > length);
652     folded = createUninitializedInternalNonEmpty(realLength, data);
653     status = U_ZERO_ERROR;
654     u_strFoldCase(data, realLength, upconvertedCharacters, length, U_FOLD_CASE_DEFAULT, &status);
655     if (U_FAILURE(status))
656         return *this;
657     return folded;
658 }
659
660 template<StringImpl::CaseConvertType type, typename CharacterType>
661 ALWAYS_INLINE Ref<StringImpl> StringImpl::convertASCIICase(StringImpl& impl, const CharacterType* data, unsigned length)
662 {
663     unsigned failingIndex;
664     for (unsigned i = 0; i < length; ++i) {
665         CharacterType character = data[i];
666         if (type == CaseConvertType::Lower ? UNLIKELY(isASCIIUpper(character)) : LIKELY(isASCIILower(character))) {
667             failingIndex = i;
668             goto SlowPath;
669         }
670     }
671     return impl;
672
673 SlowPath:
674     CharacterType* newData;
675     auto newImpl = createUninitializedInternalNonEmpty(length, newData);
676     copyCharacters(newData, data, failingIndex);
677     for (unsigned i = failingIndex; i < length; ++i)
678         newData[i] = type == CaseConvertType::Lower ? toASCIILower(data[i]) : toASCIIUpper(data[i]);
679     return newImpl;
680 }
681
682 Ref<StringImpl> StringImpl::convertToASCIILowercase()
683 {
684     if (is8Bit())
685         return convertASCIICase<CaseConvertType::Lower>(*this, m_data8, m_length);
686     return convertASCIICase<CaseConvertType::Lower>(*this, m_data16, m_length);
687 }
688
689 Ref<StringImpl> StringImpl::convertToASCIIUppercase()
690 {
691     if (is8Bit())
692         return convertASCIICase<CaseConvertType::Upper>(*this, m_data8, m_length);
693     return convertASCIICase<CaseConvertType::Upper>(*this, m_data16, m_length);
694 }
695
696 template <class UCharPredicate>
697 inline Ref<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate)
698 {
699     if (!m_length)
700         return *this;
701
702     unsigned start = 0;
703     unsigned end = m_length - 1;
704     
705     // skip white space from start
706     while (start <= end && predicate(is8Bit() ? m_data8[start] : m_data16[start]))
707         ++start;
708     
709     // only white space
710     if (start > end) 
711         return *empty();
712
713     // skip white space from end
714     while (end && predicate(is8Bit() ? m_data8[end] : m_data16[end]))
715         --end;
716
717     if (!start && end == m_length - 1)
718         return *this;
719     if (is8Bit())
720         return create(m_data8 + start, end + 1 - start);
721     return create(m_data16 + start, end + 1 - start);
722 }
723
724 class UCharPredicate {
725 public:
726     inline UCharPredicate(CharacterMatchFunctionPtr function): m_function(function) { }
727
728     inline bool operator()(UChar character) const
729     {
730         return m_function(character);
731     }
732
733 private:
734     const CharacterMatchFunctionPtr m_function;
735 };
736
737 class SpaceOrNewlinePredicate {
738 public:
739     inline bool operator()(UChar character) const
740     {
741         return isSpaceOrNewline(character);
742     }
743 };
744
745 Ref<StringImpl> StringImpl::stripWhiteSpace()
746 {
747     return stripMatchedCharacters(SpaceOrNewlinePredicate());
748 }
749
750 Ref<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
751 {
752     return stripMatchedCharacters(UCharPredicate(isWhiteSpace));
753 }
754
755 template<typename CharacterType> ALWAYS_INLINE Ref<StringImpl> StringImpl::removeCharacters(const CharacterType* characters, CharacterMatchFunctionPtr findMatch)
756 {
757     auto* from = characters;
758     auto* fromend = from + m_length;
759     
760     // Assume the common case will not remove any characters
761     while (from != fromend && !findMatch(*from))
762         ++from;
763     if (from == fromend)
764         return *this;
765     
766     StringBuffer<CharacterType> data(m_length);
767     auto* to = data.characters();
768     unsigned outc = from - characters;
769     
770     if (outc)
771         copyCharacters(to, characters, outc);
772
773     while (true) {
774         while (from != fromend && findMatch(*from))
775             ++from;
776         while (from != fromend && !findMatch(*from))
777             to[outc++] = *from++;
778         if (from == fromend)
779             break;
780     }
781
782     data.shrink(outc);
783
784     return adopt(WTFMove(data));
785 }
786
787 Ref<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)
788 {
789     if (is8Bit())
790         return removeCharacters(characters8(), findMatch);
791     return removeCharacters(characters16(), findMatch);
792 }
793
794 template<typename CharacterType, class UCharPredicate> inline Ref<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate)
795 {
796     StringBuffer<CharacterType> data(m_length);
797
798     auto* from = characters<CharacterType>();
799     auto* fromend = from + m_length;
800     int outc = 0;
801     bool changedToSpace = false;
802     
803     auto* to = data.characters();
804     
805     while (true) {
806         while (from != fromend && predicate(*from)) {
807             if (*from != ' ')
808                 changedToSpace = true;
809             ++from;
810         }
811         while (from != fromend && !predicate(*from))
812             to[outc++] = *from++;
813         if (from != fromend)
814             to[outc++] = ' ';
815         else
816             break;
817     }
818     
819     if (outc > 0 && to[outc - 1] == ' ')
820         --outc;
821     
822     if (static_cast<unsigned>(outc) == m_length && !changedToSpace)
823         return *this;
824     
825     data.shrink(outc);
826     
827     return adopt(WTFMove(data));
828 }
829
830 Ref<StringImpl> StringImpl::simplifyWhiteSpace()
831 {
832     if (is8Bit())
833         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate());
834     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate());
835 }
836
837 Ref<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
838 {
839     if (is8Bit())
840         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(UCharPredicate(isWhiteSpace));
841     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(UCharPredicate(isWhiteSpace));
842 }
843
844 int StringImpl::toIntStrict(bool* ok, int base)
845 {
846     if (is8Bit())
847         return charactersToIntStrict(characters8(), m_length, ok, base);
848     return charactersToIntStrict(characters16(), m_length, ok, base);
849 }
850
851 unsigned StringImpl::toUIntStrict(bool* ok, int base)
852 {
853     if (is8Bit())
854         return charactersToUIntStrict(characters8(), m_length, ok, base);
855     return charactersToUIntStrict(characters16(), m_length, ok, base);
856 }
857
858 int64_t StringImpl::toInt64Strict(bool* ok, int base)
859 {
860     if (is8Bit())
861         return charactersToInt64Strict(characters8(), m_length, ok, base);
862     return charactersToInt64Strict(characters16(), m_length, ok, base);
863 }
864
865 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)
866 {
867     if (is8Bit())
868         return charactersToUInt64Strict(characters8(), m_length, ok, base);
869     return charactersToUInt64Strict(characters16(), m_length, ok, base);
870 }
871
872 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)
873 {
874     if (is8Bit())
875         return charactersToIntPtrStrict(characters8(), m_length, ok, base);
876     return charactersToIntPtrStrict(characters16(), m_length, ok, base);
877 }
878
879 int StringImpl::toInt(bool* ok)
880 {
881     if (is8Bit())
882         return charactersToInt(characters8(), m_length, ok);
883     return charactersToInt(characters16(), m_length, ok);
884 }
885
886 unsigned StringImpl::toUInt(bool* ok)
887 {
888     if (is8Bit())
889         return charactersToUInt(characters8(), m_length, ok);
890     return charactersToUInt(characters16(), m_length, ok);
891 }
892
893 int64_t StringImpl::toInt64(bool* ok)
894 {
895     if (is8Bit())
896         return charactersToInt64(characters8(), m_length, ok);
897     return charactersToInt64(characters16(), m_length, ok);
898 }
899
900 uint64_t StringImpl::toUInt64(bool* ok)
901 {
902     if (is8Bit())
903         return charactersToUInt64(characters8(), m_length, ok);
904     return charactersToUInt64(characters16(), m_length, ok);
905 }
906
907 intptr_t StringImpl::toIntPtr(bool* ok)
908 {
909     if (is8Bit())
910         return charactersToIntPtr(characters8(), m_length, ok);
911     return charactersToIntPtr(characters16(), m_length, ok);
912 }
913
914 double StringImpl::toDouble(bool* ok)
915 {
916     if (is8Bit())
917         return charactersToDouble(characters8(), m_length, ok);
918     return charactersToDouble(characters16(), m_length, ok);
919 }
920
921 float StringImpl::toFloat(bool* ok)
922 {
923     if (is8Bit())
924         return charactersToFloat(characters8(), m_length, ok);
925     return charactersToFloat(characters16(), m_length, ok);
926 }
927
928 size_t StringImpl::find(CharacterMatchFunctionPtr matchFunction, unsigned start)
929 {
930     if (is8Bit())
931         return WTF::find(characters8(), m_length, matchFunction, start);
932     return WTF::find(characters16(), m_length, matchFunction, start);
933 }
934
935 size_t StringImpl::find(const LChar* matchString, unsigned index)
936 {
937     // Check for null or empty string to match against
938     if (!matchString)
939         return notFound;
940     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
941     if (matchStringLength > std::numeric_limits<unsigned>::max())
942         CRASH();
943     unsigned matchLength = matchStringLength;
944     if (!matchLength)
945         return std::min(index, length());
946
947     // Optimization 1: fast case for strings of length 1.
948     if (matchLength == 1) {
949         if (is8Bit())
950             return WTF::find(characters8(), length(), matchString[0], index);
951         return WTF::find(characters16(), length(), *matchString, index);
952     }
953
954     // Check index & matchLength are in range.
955     if (index > length())
956         return notFound;
957     unsigned searchLength = length() - index;
958     if (matchLength > searchLength)
959         return notFound;
960     // delta is the number of additional times to test; delta == 0 means test only once.
961     unsigned delta = searchLength - matchLength;
962
963     // Optimization 2: keep a running hash of the strings,
964     // only call equal if the hashes match.
965
966     if (is8Bit()) {
967         const LChar* searchCharacters = characters8() + index;
968
969         unsigned searchHash = 0;
970         unsigned matchHash = 0;
971         for (unsigned i = 0; i < matchLength; ++i) {
972             searchHash += searchCharacters[i];
973             matchHash += matchString[i];
974         }
975
976         unsigned i = 0;
977         while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
978             if (i == delta)
979                 return notFound;
980             searchHash += searchCharacters[i + matchLength];
981             searchHash -= searchCharacters[i];
982             ++i;
983         }
984         return index + i;
985     }
986
987     const UChar* searchCharacters = characters16() + index;
988
989     unsigned searchHash = 0;
990     unsigned matchHash = 0;
991     for (unsigned i = 0; i < matchLength; ++i) {
992         searchHash += searchCharacters[i];
993         matchHash += matchString[i];
994     }
995
996     unsigned i = 0;
997     while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
998         if (i == delta)
999             return notFound;
1000         searchHash += searchCharacters[i + matchLength];
1001         searchHash -= searchCharacters[i];
1002         ++i;
1003     }
1004     return index + i;
1005 }
1006
1007 size_t StringImpl::find(StringImpl* matchString)
1008 {
1009     // Check for null string to match against
1010     if (UNLIKELY(!matchString))
1011         return notFound;
1012     unsigned matchLength = matchString->length();
1013
1014     // Optimization 1: fast case for strings of length 1.
1015     if (matchLength == 1) {
1016         if (is8Bit()) {
1017             if (matchString->is8Bit())
1018                 return WTF::find(characters8(), length(), matchString->characters8()[0]);
1019             return WTF::find(characters8(), length(), matchString->characters16()[0]);
1020         }
1021         if (matchString->is8Bit())
1022             return WTF::find(characters16(), length(), matchString->characters8()[0]);
1023         return WTF::find(characters16(), length(), matchString->characters16()[0]);
1024     }
1025
1026     // Check matchLength is in range.
1027     if (matchLength > length())
1028         return notFound;
1029
1030     // Check for empty string to match against
1031     if (UNLIKELY(!matchLength))
1032         return 0;
1033
1034     if (is8Bit()) {
1035         if (matchString->is8Bit())
1036             return findInner(characters8(), matchString->characters8(), 0, length(), matchLength);
1037         return findInner(characters8(), matchString->characters16(), 0, length(), matchLength);
1038     }
1039
1040     if (matchString->is8Bit())
1041         return findInner(characters16(), matchString->characters8(), 0, length(), matchLength);
1042
1043     return findInner(characters16(), matchString->characters16(), 0, length(), matchLength);
1044 }
1045
1046 size_t StringImpl::find(StringImpl* matchString, unsigned index)
1047 {
1048     // Check for null or empty string to match against
1049     if (UNLIKELY(!matchString))
1050         return notFound;
1051
1052     return findCommon(*this, *matchString, index);
1053 }
1054
1055 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString) const
1056 {
1057     return ::WTF::findIgnoringASCIICase(*this, matchString, 0);
1058 }
1059
1060 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString, unsigned startOffset) const
1061 {
1062     return ::WTF::findIgnoringASCIICase(*this, matchString, startOffset);
1063 }
1064
1065 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString) const
1066 {
1067     if (!matchString)
1068         return notFound;
1069     return ::WTF::findIgnoringASCIICase(*this, *matchString, 0);
1070 }
1071
1072 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString, unsigned startOffset) const
1073 {
1074     if (!matchString)
1075         return notFound;
1076     return ::WTF::findIgnoringASCIICase(*this, *matchString, startOffset);
1077 }
1078
1079 size_t StringImpl::reverseFind(UChar character, unsigned index)
1080 {
1081     if (is8Bit())
1082         return WTF::reverseFind(characters8(), m_length, character, index);
1083     return WTF::reverseFind(characters16(), m_length, character, index);
1084 }
1085
1086 template <typename SearchCharacterType, typename MatchCharacterType>
1087 ALWAYS_INLINE static size_t reverseFindInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
1088 {
1089     // Optimization: keep a running hash of the strings,
1090     // only call equal if the hashes match.
1091
1092     // delta is the number of additional times to test; delta == 0 means test only once.
1093     unsigned delta = std::min(index, length - matchLength);
1094     
1095     unsigned searchHash = 0;
1096     unsigned matchHash = 0;
1097     for (unsigned i = 0; i < matchLength; ++i) {
1098         searchHash += searchCharacters[delta + i];
1099         matchHash += matchCharacters[i];
1100     }
1101
1102     // keep looping until we match
1103     while (searchHash != matchHash || !equal(searchCharacters + delta, matchCharacters, matchLength)) {
1104         if (!delta)
1105             return notFound;
1106         --delta;
1107         searchHash -= searchCharacters[delta + matchLength];
1108         searchHash += searchCharacters[delta];
1109     }
1110     return delta;
1111 }
1112
1113 size_t StringImpl::reverseFind(StringImpl* matchString, unsigned index)
1114 {
1115     // Check for null or empty string to match against
1116     if (!matchString)
1117         return notFound;
1118     unsigned matchLength = matchString->length();
1119     unsigned ourLength = length();
1120     if (!matchLength)
1121         return std::min(index, ourLength);
1122
1123     // Optimization 1: fast case for strings of length 1.
1124     if (matchLength == 1) {
1125         if (is8Bit())
1126             return WTF::reverseFind(characters8(), ourLength, (*matchString)[0], index);
1127         return WTF::reverseFind(characters16(), ourLength, (*matchString)[0], index);
1128     }
1129
1130     // Check index & matchLength are in range.
1131     if (matchLength > ourLength)
1132         return notFound;
1133
1134     if (is8Bit()) {
1135         if (matchString->is8Bit())
1136             return reverseFindInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1137         return reverseFindInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1138     }
1139     
1140     if (matchString->is8Bit())
1141         return reverseFindInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1142
1143     return reverseFindInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1144 }
1145
1146 ALWAYS_INLINE static bool equalInner(const StringImpl& string, unsigned startOffset, const char* matchString, unsigned matchLength)
1147 {
1148     ASSERT(matchLength <= string.length());
1149     ASSERT(startOffset + matchLength <= string.length());
1150
1151     if (string.is8Bit())
1152         return equal(string.characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1153     return equal(string.characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1154 }
1155
1156 ALWAYS_INLINE static bool equalInner(const StringImpl& string, unsigned startOffset, const StringImpl& matchString)
1157 {
1158     if (startOffset > string.length())
1159         return false;
1160     if (matchString.length() > string.length())
1161         return false;
1162     if (matchString.length() + startOffset > string.length())
1163         return false;
1164
1165     if (string.is8Bit()) {
1166         if (matchString.is8Bit())
1167             return equal(string.characters8() + startOffset, matchString.characters8(), matchString.length());
1168         return equal(string.characters8() + startOffset, matchString.characters16(), matchString.length());
1169     }
1170     if (matchString.is8Bit())
1171         return equal(string.characters16() + startOffset, matchString.characters8(), matchString.length());
1172     return equal(string.characters16() + startOffset, matchString.characters16(), matchString.length());
1173 }
1174
1175 bool StringImpl::startsWith(const StringImpl* string) const
1176 {
1177     return string && ::WTF::startsWith(*this, *string);
1178 }
1179
1180 bool StringImpl::startsWith(const StringImpl& string) const
1181 {
1182     return ::WTF::startsWith(*this, string);
1183 }
1184
1185 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl* prefix) const
1186 {
1187     return prefix && ::WTF::startsWithIgnoringASCIICase(*this, *prefix);
1188 }
1189
1190 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl& prefix) const
1191 {
1192     return ::WTF::startsWithIgnoringASCIICase(*this, prefix);
1193 }
1194
1195 bool StringImpl::startsWith(UChar character) const
1196 {
1197     return m_length && (*this)[0] == character;
1198 }
1199
1200 bool StringImpl::startsWith(const char* matchString, unsigned matchLength) const
1201 {
1202     return matchLength <= length() && equalInner(*this, 0, matchString, matchLength);
1203 }
1204
1205 bool StringImpl::hasInfixStartingAt(const StringImpl& matchString, unsigned startOffset) const
1206 {
1207     return equalInner(*this, startOffset, matchString);
1208 }
1209
1210 bool StringImpl::endsWith(StringImpl* suffix)
1211 {
1212     return suffix && ::WTF::endsWith(*this, *suffix);
1213 }
1214
1215 bool StringImpl::endsWith(StringImpl& suffix)
1216 {
1217     return ::WTF::endsWith(*this, suffix);
1218 }
1219
1220 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl* suffix) const
1221 {
1222     return suffix && ::WTF::endsWithIgnoringASCIICase(*this, *suffix);
1223 }
1224
1225 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl& suffix) const
1226 {
1227     return ::WTF::endsWithIgnoringASCIICase(*this, suffix);
1228 }
1229
1230 bool StringImpl::endsWith(UChar character) const
1231 {
1232     return m_length && (*this)[m_length - 1] == character;
1233 }
1234
1235 bool StringImpl::endsWith(const char* matchString, unsigned matchLength) const
1236 {
1237     return matchLength <= length() && equalInner(*this, length() - matchLength, matchString, matchLength);
1238 }
1239
1240 bool StringImpl::hasInfixEndingAt(const StringImpl& matchString, unsigned endOffset) const
1241 {
1242     return endOffset >= matchString.length() && equalInner(*this, endOffset - matchString.length(), matchString);
1243 }
1244
1245 Ref<StringImpl> StringImpl::replace(UChar target, UChar replacement)
1246 {
1247     if (target == replacement)
1248         return *this;
1249     unsigned i;
1250     for (i = 0; i != m_length; ++i) {
1251         UChar character = is8Bit() ? m_data8[i] : m_data16[i];
1252         if (character == target)
1253             break;
1254     }
1255     if (i == m_length)
1256         return *this;
1257
1258     if (is8Bit()) {
1259         if (target > 0xFF) {
1260             // Looking for a 16-bit character in an 8-bit string, so we're done.
1261             return *this;
1262         }
1263
1264         if (replacement <= 0xFF) {
1265             LChar* data;
1266             LChar oldChar = static_cast<LChar>(target);
1267             LChar newChar = static_cast<LChar>(replacement);
1268
1269             auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1270
1271             for (i = 0; i != m_length; ++i) {
1272                 LChar character = m_data8[i];
1273                 if (character == oldChar)
1274                     character = newChar;
1275                 data[i] = character;
1276             }
1277             return newImpl;
1278         }
1279
1280         UChar* data;
1281         auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1282
1283         for (i = 0; i != m_length; ++i) {
1284             UChar character = m_data8[i];
1285             if (character == target)
1286                 character = replacement;
1287             data[i] = character;
1288         }
1289
1290         return newImpl;
1291     }
1292
1293     UChar* data;
1294     auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1295
1296     for (i = 0; i != m_length; ++i) {
1297         UChar character = m_data16[i];
1298         if (character == target)
1299             character = replacement;
1300         data[i] = character;
1301     }
1302     return newImpl;
1303 }
1304
1305 Ref<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* string)
1306 {
1307     position = std::min(position, length());
1308     lengthToReplace = std::min(lengthToReplace, length() - position);
1309     unsigned lengthToInsert = string ? string->length() : 0;
1310     if (!lengthToReplace && !lengthToInsert)
1311         return *this;
1312
1313     if ((length() - lengthToReplace) >= (std::numeric_limits<unsigned>::max() - lengthToInsert))
1314         CRASH();
1315
1316     if (is8Bit() && (!string || string->is8Bit())) {
1317         LChar* data;
1318         auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1319         copyCharacters(data, m_data8, position);
1320         if (string)
1321             copyCharacters(data + position, string->m_data8, lengthToInsert);
1322         copyCharacters(data + position + lengthToInsert, m_data8 + position + lengthToReplace, length() - position - lengthToReplace);
1323         return newImpl;
1324     }
1325     UChar* data;
1326     auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1327     if (is8Bit())
1328         copyCharacters(data, m_data8, position);
1329     else
1330         copyCharacters(data, m_data16, position);
1331     if (string) {
1332         if (string->is8Bit())
1333             copyCharacters(data + position, string->m_data8, lengthToInsert);
1334         else
1335             copyCharacters(data + position, string->m_data16, lengthToInsert);
1336     }
1337     if (is8Bit())
1338         copyCharacters(data + position + lengthToInsert, m_data8 + position + lengthToReplace, length() - position - lengthToReplace);
1339     else
1340         copyCharacters(data + position + lengthToInsert, m_data16 + position + lengthToReplace, length() - position - lengthToReplace);
1341     return newImpl;
1342 }
1343
1344 Ref<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
1345 {
1346     if (!replacement)
1347         return *this;
1348     if (replacement->is8Bit())
1349         return replace(pattern, replacement->m_data8, replacement->length());
1350     return replace(pattern, replacement->m_data16, replacement->length());
1351 }
1352
1353 Ref<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength)
1354 {
1355     ASSERT(replacement);
1356
1357     size_t srcSegmentStart = 0;
1358     unsigned matchCount = 0;
1359
1360     // Count the matches.
1361     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1362         ++matchCount;
1363         ++srcSegmentStart;
1364     }
1365
1366     // If we have 0 matches then we don't have to do any more work.
1367     if (!matchCount)
1368         return *this;
1369
1370     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1371         CRASH();
1372
1373     unsigned replaceSize = matchCount * repStrLength;
1374     unsigned newSize = m_length - matchCount;
1375     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1376         CRASH();
1377
1378     newSize += replaceSize;
1379
1380     // Construct the new data.
1381     size_t srcSegmentEnd;
1382     unsigned srcSegmentLength;
1383     srcSegmentStart = 0;
1384     unsigned dstOffset = 0;
1385
1386     if (is8Bit()) {
1387         LChar* data;
1388         auto newImpl = createUninitialized(newSize, data);
1389
1390         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1391             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1392             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1393             dstOffset += srcSegmentLength;
1394             copyCharacters(data + dstOffset, replacement, repStrLength);
1395             dstOffset += repStrLength;
1396             srcSegmentStart = srcSegmentEnd + 1;
1397         }
1398
1399         srcSegmentLength = m_length - srcSegmentStart;
1400         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1401
1402         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1403
1404         return newImpl;
1405     }
1406
1407     UChar* data;
1408     auto newImpl = createUninitialized(newSize, data);
1409
1410     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1411         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1412         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1413
1414         dstOffset += srcSegmentLength;
1415         copyCharacters(data + dstOffset, replacement, repStrLength);
1416
1417         dstOffset += repStrLength;
1418         srcSegmentStart = srcSegmentEnd + 1;
1419     }
1420
1421     srcSegmentLength = m_length - srcSegmentStart;
1422     copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1423
1424     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1425
1426     return newImpl;
1427 }
1428
1429 Ref<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength)
1430 {
1431     ASSERT(replacement);
1432
1433     size_t srcSegmentStart = 0;
1434     unsigned matchCount = 0;
1435
1436     // Count the matches.
1437     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1438         ++matchCount;
1439         ++srcSegmentStart;
1440     }
1441
1442     // If we have 0 matches then we don't have to do any more work.
1443     if (!matchCount)
1444         return *this;
1445
1446     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1447         CRASH();
1448
1449     unsigned replaceSize = matchCount * repStrLength;
1450     unsigned newSize = m_length - matchCount;
1451     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1452         CRASH();
1453
1454     newSize += replaceSize;
1455
1456     // Construct the new data.
1457     size_t srcSegmentEnd;
1458     unsigned srcSegmentLength;
1459     srcSegmentStart = 0;
1460     unsigned dstOffset = 0;
1461
1462     if (is8Bit()) {
1463         UChar* data;
1464         auto newImpl = createUninitialized(newSize, data);
1465
1466         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1467             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1468             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1469
1470             dstOffset += srcSegmentLength;
1471             copyCharacters(data + dstOffset, replacement, repStrLength);
1472
1473             dstOffset += repStrLength;
1474             srcSegmentStart = srcSegmentEnd + 1;
1475         }
1476
1477         srcSegmentLength = m_length - srcSegmentStart;
1478         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1479
1480         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1481
1482         return newImpl;
1483     }
1484
1485     UChar* data;
1486     auto newImpl = createUninitialized(newSize, data);
1487
1488     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1489         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1490         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1491
1492         dstOffset += srcSegmentLength;
1493         copyCharacters(data + dstOffset, replacement, repStrLength);
1494
1495         dstOffset += repStrLength;
1496         srcSegmentStart = srcSegmentEnd + 1;
1497     }
1498
1499     srcSegmentLength = m_length - srcSegmentStart;
1500     copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1501
1502     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1503
1504     return newImpl;
1505 }
1506
1507 Ref<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
1508 {
1509     if (!pattern || !replacement)
1510         return *this;
1511
1512     unsigned patternLength = pattern->length();
1513     if (!patternLength)
1514         return *this;
1515         
1516     unsigned repStrLength = replacement->length();
1517     size_t srcSegmentStart = 0;
1518     unsigned matchCount = 0;
1519     
1520     // Count the matches.
1521     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1522         ++matchCount;
1523         srcSegmentStart += patternLength;
1524     }
1525     
1526     // If we have 0 matches, we don't have to do any more work
1527     if (!matchCount)
1528         return *this;
1529     
1530     unsigned newSize = m_length - matchCount * patternLength;
1531     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1532         CRASH();
1533
1534     if (newSize > (std::numeric_limits<unsigned>::max() - matchCount * repStrLength))
1535         CRASH();
1536
1537     newSize += matchCount * repStrLength;
1538
1539     
1540     // Construct the new data
1541     size_t srcSegmentEnd;
1542     unsigned srcSegmentLength;
1543     srcSegmentStart = 0;
1544     unsigned dstOffset = 0;
1545     bool srcIs8Bit = is8Bit();
1546     bool replacementIs8Bit = replacement->is8Bit();
1547     
1548     // There are 4 cases:
1549     // 1. This and replacement are both 8 bit.
1550     // 2. This and replacement are both 16 bit.
1551     // 3. This is 8 bit and replacement is 16 bit.
1552     // 4. This is 16 bit and replacement is 8 bit.
1553     if (srcIs8Bit && replacementIs8Bit) {
1554         // Case 1
1555         LChar* data;
1556         auto newImpl = createUninitialized(newSize, data);
1557         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1558             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1559             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1560             dstOffset += srcSegmentLength;
1561             copyCharacters(data + dstOffset, replacement->m_data8, repStrLength);
1562             dstOffset += repStrLength;
1563             srcSegmentStart = srcSegmentEnd + patternLength;
1564         }
1565
1566         srcSegmentLength = m_length - srcSegmentStart;
1567         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1568
1569         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1570
1571         return newImpl;
1572     }
1573
1574     UChar* data;
1575     auto newImpl = createUninitialized(newSize, data);
1576     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1577         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1578         if (srcIs8Bit) {
1579             // Case 3.
1580             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1581         } else {
1582             // Case 2 & 4.
1583             copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1584         }
1585         dstOffset += srcSegmentLength;
1586         if (replacementIs8Bit) {
1587             // Cases 2 & 3.
1588             copyCharacters(data + dstOffset, replacement->m_data8, repStrLength);
1589         } else {
1590             // Case 4
1591             copyCharacters(data + dstOffset, replacement->m_data16, repStrLength);
1592         }
1593         dstOffset += repStrLength;
1594         srcSegmentStart = srcSegmentEnd + patternLength;
1595     }
1596
1597     srcSegmentLength = m_length - srcSegmentStart;
1598     if (srcIs8Bit) {
1599         // Case 3.
1600         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1601     } else {
1602         // Cases 2 & 4.
1603         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1604     }
1605
1606     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1607
1608     return newImpl;
1609 }
1610
1611 bool equal(const StringImpl* a, const StringImpl* b)
1612 {
1613     return equalCommon(a, b);
1614 }
1615
1616 template<typename CharacterType> inline bool equalInternal(const StringImpl* a, const CharacterType* b, unsigned length)
1617 {
1618     if (!a)
1619         return !b;
1620     if (!b)
1621         return false;
1622
1623     if (a->length() != length)
1624         return false;
1625     if (a->is8Bit())
1626         return equal(a->characters8(), b, length);
1627     return equal(a->characters16(), b, length);
1628 }
1629
1630 bool equal(const StringImpl* a, const LChar* b, unsigned length)
1631 {
1632     return equalInternal(a, b, length);
1633 }
1634
1635 bool equal(const StringImpl* a, const UChar* b, unsigned length)
1636 {
1637     return equalInternal(a, b, length);
1638 }
1639
1640 bool equal(const StringImpl* a, const LChar* b)
1641 {
1642     if (!a)
1643         return !b;
1644     if (!b)
1645         return !a;
1646
1647     unsigned length = a->length();
1648
1649     if (a->is8Bit()) {
1650         const LChar* aPtr = a->characters8();
1651         for (unsigned i = 0; i != length; ++i) {
1652             LChar bc = b[i];
1653             LChar ac = aPtr[i];
1654             if (!bc)
1655                 return false;
1656             if (ac != bc)
1657                 return false;
1658         }
1659
1660         return !b[length];
1661     }
1662
1663     const UChar* aPtr = a->characters16();
1664     for (unsigned i = 0; i != length; ++i) {
1665         LChar bc = b[i];
1666         if (!bc)
1667             return false;
1668         if (aPtr[i] != bc)
1669             return false;
1670     }
1671
1672     return !b[length];
1673 }
1674
1675 bool equal(const StringImpl& a, const StringImpl& b)
1676 {
1677     return equalCommon(a, b);
1678 }
1679
1680 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
1681 {
1682     if (!a && b && !b->length())
1683         return true;
1684     if (!b && a && !a->length())
1685         return true;
1686     return equal(a, b);
1687 }
1688
1689 bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl* b)
1690 {
1691     return a == b || (a && b && equalIgnoringASCIICase(*a, *b));
1692 }
1693
1694 bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b)
1695 {
1696     ASSERT(a);
1697     ASSERT(b);
1698     return equalIgnoringASCIICase(*a, *b);
1699 }
1700
1701 UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality)
1702 {
1703     for (unsigned i = 0; i < m_length; ++i) {
1704         auto charDirection = u_charDirection(is8Bit() ? m_data8[i] : m_data16[i]);
1705         if (charDirection == U_LEFT_TO_RIGHT) {
1706             if (hasStrongDirectionality)
1707                 *hasStrongDirectionality = true;
1708             return U_LEFT_TO_RIGHT;
1709         }
1710         if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
1711             if (hasStrongDirectionality)
1712                 *hasStrongDirectionality = true;
1713             return U_RIGHT_TO_LEFT;
1714         }
1715     }
1716     if (hasStrongDirectionality)
1717         *hasStrongDirectionality = false;
1718     return U_LEFT_TO_RIGHT;
1719 }
1720
1721 Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>&& buffer)
1722 {
1723     unsigned length = buffer.length();
1724     if (!length)
1725         return *empty();
1726     return adoptRef(*new StringImpl(buffer.release(), length));
1727 }
1728
1729 Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>&& buffer)
1730 {
1731     unsigned length = buffer.length();
1732     if (!length)
1733         return *empty();
1734     return adoptRef(*new StringImpl(buffer.release(), length));
1735 }
1736
1737 size_t StringImpl::sizeInBytes() const
1738 {
1739     // FIXME: support substrings
1740     size_t size = length();
1741     if (!is8Bit())
1742         size *= 2;
1743     return size + sizeof(*this);
1744 }
1745
1746 // Helper to write a three-byte UTF-8 code point into the buffer; caller must ensure room is available.
1747 static inline void putUTF8Triple(char*& buffer, UChar character)
1748 {
1749     ASSERT(character >= 0x0800);
1750     *buffer++ = static_cast<char>(((character >> 12) & 0x0F) | 0xE0);
1751     *buffer++ = static_cast<char>(((character >> 6) & 0x3F) | 0x80);
1752     *buffer++ = static_cast<char>((character & 0x3F) | 0x80);
1753 }
1754
1755 bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode)
1756 {
1757     if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) {
1758         const UChar* charactersEnd = characters + length;
1759         char* bufferEnd = buffer + bufferSize;
1760         while (characters < charactersEnd) {
1761             // Use strict conversion to detect unpaired surrogates.
1762             ConversionResult result = convertUTF16ToUTF8(&characters, charactersEnd, &buffer, bufferEnd, true);
1763             ASSERT(result != targetExhausted);
1764             // Conversion fails when there is an unpaired surrogate.
1765             // Put replacement character (U+FFFD) instead of the unpaired surrogate.
1766             if (result != conversionOK) {
1767                 ASSERT((0xD800 <= *characters && *characters <= 0xDFFF));
1768                 // There should be room left, since one UChar hasn't been converted.
1769                 ASSERT((buffer + 3) <= bufferEnd);
1770                 putUTF8Triple(buffer, replacementCharacter);
1771                 ++characters;
1772             }
1773         }
1774     } else {
1775         bool strict = mode == StrictConversion;
1776         const UChar* originalCharacters = characters;
1777         ConversionResult result = convertUTF16ToUTF8(&characters, characters + length, &buffer, buffer + bufferSize, strict);
1778         ASSERT(result != targetExhausted); // (length * 3) should be sufficient for any conversion
1779
1780         // Only produced from strict conversion.
1781         if (result == sourceIllegal) {
1782             ASSERT(strict);
1783             return false;
1784         }
1785
1786         // Check for an unconverted high surrogate.
1787         if (result == sourceExhausted) {
1788             if (strict)
1789                 return false;
1790             // This should be one unpaired high surrogate. Treat it the same
1791             // was as an unpaired high surrogate would have been handled in
1792             // the middle of a string with non-strict conversion - which is
1793             // to say, simply encode it to UTF-8.
1794             ASSERT_UNUSED(
1795                 originalCharacters, (characters + 1) == (originalCharacters + length));
1796             ASSERT((*characters >= 0xD800) && (*characters <= 0xDBFF));
1797             // There should be room left, since one UChar hasn't been converted.
1798             ASSERT((buffer + 3) <= (buffer + bufferSize));
1799             putUTF8Triple(buffer, *characters);
1800         }
1801     }
1802     
1803     return true;
1804 }
1805
1806 CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length)
1807 {
1808     if (!length)
1809         return CString("", 0);
1810     if (length > std::numeric_limits<unsigned>::max() / 3)
1811         return CString();
1812     Vector<char, 1024> bufferVector(length * 3);
1813     char* buffer = bufferVector.data();
1814     const LChar* source = characters;
1815     ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size());
1816     ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
1817     return CString(bufferVector.data(), buffer - bufferVector.data());
1818 }
1819
1820 CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode)
1821 {
1822     if (!length)
1823         return CString("", 0);
1824     if (length > std::numeric_limits<unsigned>::max() / 3)
1825         return CString();
1826     Vector<char, 1024> bufferVector(length * 3);
1827     char* buffer = bufferVector.data();
1828     if (!utf8Impl(characters, length, buffer, bufferVector.size(), mode))
1829         return CString();
1830     return CString(bufferVector.data(), buffer - bufferVector.data());
1831 }
1832
1833 CString StringImpl::utf8ForRange(unsigned offset, unsigned length, ConversionMode mode) const
1834 {
1835     ASSERT(offset <= this->length());
1836     ASSERT(offset + length <= this->length());
1837     
1838     if (!length)
1839         return CString("", 0);
1840
1841     // Allocate a buffer big enough to hold all the characters
1842     // (an individual UTF-16 UChar can only expand to 3 UTF-8 bytes).
1843     // Optimization ideas, if we find this function is hot:
1844     //  * We could speculatively create a CStringBuffer to contain 'length' 
1845     //    characters, and resize if necessary (i.e. if the buffer contains
1846     //    non-ascii characters). (Alternatively, scan the buffer first for
1847     //    ascii characters, so we know this will be sufficient).
1848     //  * We could allocate a CStringBuffer with an appropriate size to
1849     //    have a good chance of being able to write the string into the
1850     //    buffer without reallocing (say, 1.5 x length).
1851     if (length > std::numeric_limits<unsigned>::max() / 3)
1852         return CString();
1853     Vector<char, 1024> bufferVector(length * 3);
1854
1855     char* buffer = bufferVector.data();
1856
1857     if (is8Bit()) {
1858         const LChar* characters = this->characters8() + offset;
1859
1860         ConversionResult result = convertLatin1ToUTF8(&characters, characters + length, &buffer, buffer + bufferVector.size());
1861         ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
1862     } else {
1863         if (!utf8Impl(this->characters16() + offset, length, buffer, bufferVector.size(), mode))
1864             return CString();
1865     }
1866
1867     return CString(bufferVector.data(), buffer - bufferVector.data());
1868 }
1869
1870 CString StringImpl::utf8(ConversionMode mode) const
1871 {
1872     return utf8ForRange(0, length(), mode);
1873 }
1874
1875 NEVER_INLINE unsigned StringImpl::hashSlowCase() const
1876 {
1877     if (is8Bit())
1878         setHash(StringHasher::computeHashAndMaskTop8Bits(m_data8, m_length));
1879     else
1880         setHash(StringHasher::computeHashAndMaskTop8Bits(m_data16, m_length));
1881     return existingHash();
1882 }
1883
1884 unsigned StringImpl::concurrentHash() const
1885 {
1886     unsigned hash;
1887     if (is8Bit())
1888         hash = StringHasher::computeHashAndMaskTop8Bits(m_data8, m_length);
1889     else
1890         hash = StringHasher::computeHashAndMaskTop8Bits(m_data16, m_length);
1891     ASSERT(((hash << s_flagCount) >> s_flagCount) == hash);
1892     return hash;
1893 }
1894
1895 bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b)
1896 {
1897     if (!b)
1898         return !aLength;
1899     if (aLength != b->length())
1900         return false;
1901     if (b->is8Bit()) {
1902         const LChar* bCharacters = b->characters8();
1903         for (unsigned i = 0; i < aLength; ++i) {
1904             if (a[i] != bCharacters[i])
1905                 return false;
1906         }
1907         return true;
1908     }
1909     return !memcmp(a, b->characters16(), b->length() * sizeof(UChar));
1910 }
1911
1912 void StringImpl::releaseAssertCaged() const
1913 {
1914     if (isStatic())
1915         return;
1916     RELEASE_ASSERT(!GIGACAGE_ENABLED || Gigacage::isCaged(Gigacage::String, this));
1917     if (bufferOwnership() != BufferOwned)
1918         return;
1919     RELEASE_ASSERT(!GIGACAGE_ENABLED || Gigacage::isCaged(Gigacage::String, m_data8));
1920 }
1921
1922 } // namespace WTF