Fix some minor problems in the StringImpl header
[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<typename CodeUnitPredicate> inline Ref<StringImpl> StringImpl::stripMatchedCharacters(CodeUnitPredicate predicate)
697 {
698     if (!m_length)
699         return *this;
700
701     unsigned start = 0;
702     unsigned end = m_length - 1;
703     
704     // skip white space from start
705     while (start <= end && predicate(is8Bit() ? m_data8[start] : m_data16[start]))
706         ++start;
707     
708     // only white space
709     if (start > end) 
710         return *empty();
711
712     // skip white space from end
713     while (end && predicate(is8Bit() ? m_data8[end] : m_data16[end]))
714         --end;
715
716     if (!start && end == m_length - 1)
717         return *this;
718     if (is8Bit())
719         return create(m_data8 + start, end + 1 - start);
720     return create(m_data16 + start, end + 1 - start);
721 }
722
723 Ref<StringImpl> StringImpl::stripWhiteSpace()
724 {
725     return stripMatchedCharacters(isSpaceOrNewline);
726 }
727
728 Ref<StringImpl> StringImpl::stripLeadingAndTrailingCharacters(CodeUnitMatchFunction predicate)
729 {
730     return stripMatchedCharacters(predicate);
731 }
732
733 template<typename CharacterType> ALWAYS_INLINE Ref<StringImpl> StringImpl::removeCharacters(const CharacterType* characters, CodeUnitMatchFunction findMatch)
734 {
735     auto* from = characters;
736     auto* fromEnd = from + m_length;
737
738     // Assume the common case will not remove any characters
739     while (from != fromEnd && !findMatch(*from))
740         ++from;
741     if (from == fromEnd)
742         return *this;
743
744     StringBuffer<CharacterType> data(m_length);
745     auto* to = data.characters();
746     unsigned outc = from - characters;
747
748     if (outc)
749         copyCharacters(to, characters, outc);
750
751     do {
752         while (from != fromEnd && findMatch(*from))
753             ++from;
754         while (from != fromEnd && !findMatch(*from))
755             to[outc++] = *from++;
756     } while (from != fromEnd);
757
758     data.shrink(outc);
759
760     return adopt(WTFMove(data));
761 }
762
763 Ref<StringImpl> StringImpl::removeCharacters(CodeUnitMatchFunction findMatch)
764 {
765     if (is8Bit())
766         return removeCharacters(characters8(), findMatch);
767     return removeCharacters(characters16(), findMatch);
768 }
769
770 template<typename CharacterType, class UCharPredicate> inline Ref<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate)
771 {
772     StringBuffer<CharacterType> data(m_length);
773
774     auto* from = characters<CharacterType>();
775     auto* fromEnd = from + m_length;
776     unsigned outc = 0;
777     bool changedToSpace = false;
778     
779     auto* to = data.characters();
780     
781     while (true) {
782         while (from != fromEnd && predicate(*from)) {
783             if (*from != ' ')
784                 changedToSpace = true;
785             ++from;
786         }
787         while (from != fromEnd && !predicate(*from))
788             to[outc++] = *from++;
789         if (from != fromEnd)
790             to[outc++] = ' ';
791         else
792             break;
793     }
794
795     if (outc && to[outc - 1] == ' ')
796         --outc;
797
798     if (outc == m_length && !changedToSpace)
799         return *this;
800
801     data.shrink(outc);
802
803     return adopt(WTFMove(data));
804 }
805
806 Ref<StringImpl> StringImpl::simplifyWhiteSpace()
807 {
808     if (is8Bit())
809         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(isSpaceOrNewline);
810     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(isSpaceOrNewline);
811 }
812
813 Ref<StringImpl> StringImpl::simplifyWhiteSpace(CodeUnitMatchFunction isWhiteSpace)
814 {
815     if (is8Bit())
816         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(isWhiteSpace);
817     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(isWhiteSpace);
818 }
819
820 int StringImpl::toIntStrict(bool* ok, int base)
821 {
822     if (is8Bit())
823         return charactersToIntStrict(characters8(), m_length, ok, base);
824     return charactersToIntStrict(characters16(), m_length, ok, base);
825 }
826
827 unsigned StringImpl::toUIntStrict(bool* ok, int base)
828 {
829     if (is8Bit())
830         return charactersToUIntStrict(characters8(), m_length, ok, base);
831     return charactersToUIntStrict(characters16(), m_length, ok, base);
832 }
833
834 int64_t StringImpl::toInt64Strict(bool* ok, int base)
835 {
836     if (is8Bit())
837         return charactersToInt64Strict(characters8(), m_length, ok, base);
838     return charactersToInt64Strict(characters16(), m_length, ok, base);
839 }
840
841 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)
842 {
843     if (is8Bit())
844         return charactersToUInt64Strict(characters8(), m_length, ok, base);
845     return charactersToUInt64Strict(characters16(), m_length, ok, base);
846 }
847
848 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)
849 {
850     if (is8Bit())
851         return charactersToIntPtrStrict(characters8(), m_length, ok, base);
852     return charactersToIntPtrStrict(characters16(), m_length, ok, base);
853 }
854
855 int StringImpl::toInt(bool* ok)
856 {
857     if (is8Bit())
858         return charactersToInt(characters8(), m_length, ok);
859     return charactersToInt(characters16(), m_length, ok);
860 }
861
862 unsigned StringImpl::toUInt(bool* ok)
863 {
864     if (is8Bit())
865         return charactersToUInt(characters8(), m_length, ok);
866     return charactersToUInt(characters16(), m_length, ok);
867 }
868
869 int64_t StringImpl::toInt64(bool* ok)
870 {
871     if (is8Bit())
872         return charactersToInt64(characters8(), m_length, ok);
873     return charactersToInt64(characters16(), m_length, ok);
874 }
875
876 uint64_t StringImpl::toUInt64(bool* ok)
877 {
878     if (is8Bit())
879         return charactersToUInt64(characters8(), m_length, ok);
880     return charactersToUInt64(characters16(), m_length, ok);
881 }
882
883 intptr_t StringImpl::toIntPtr(bool* ok)
884 {
885     if (is8Bit())
886         return charactersToIntPtr(characters8(), m_length, ok);
887     return charactersToIntPtr(characters16(), m_length, ok);
888 }
889
890 double StringImpl::toDouble(bool* ok)
891 {
892     if (is8Bit())
893         return charactersToDouble(characters8(), m_length, ok);
894     return charactersToDouble(characters16(), m_length, ok);
895 }
896
897 float StringImpl::toFloat(bool* ok)
898 {
899     if (is8Bit())
900         return charactersToFloat(characters8(), m_length, ok);
901     return charactersToFloat(characters16(), m_length, ok);
902 }
903
904 size_t StringImpl::find(CodeUnitMatchFunction matchFunction, unsigned start)
905 {
906     if (is8Bit())
907         return WTF::find(characters8(), m_length, matchFunction, start);
908     return WTF::find(characters16(), m_length, matchFunction, start);
909 }
910
911 size_t StringImpl::find(const LChar* matchString, unsigned index)
912 {
913     // Check for null or empty string to match against
914     if (!matchString)
915         return notFound;
916     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
917     if (matchStringLength > std::numeric_limits<unsigned>::max())
918         CRASH();
919     unsigned matchLength = matchStringLength;
920     if (!matchLength)
921         return std::min(index, length());
922
923     // Optimization 1: fast case for strings of length 1.
924     if (matchLength == 1) {
925         if (is8Bit())
926             return WTF::find(characters8(), length(), matchString[0], index);
927         return WTF::find(characters16(), length(), *matchString, index);
928     }
929
930     // Check index & matchLength are in range.
931     if (index > length())
932         return notFound;
933     unsigned searchLength = length() - index;
934     if (matchLength > searchLength)
935         return notFound;
936     // delta is the number of additional times to test; delta == 0 means test only once.
937     unsigned delta = searchLength - matchLength;
938
939     // Optimization 2: keep a running hash of the strings,
940     // only call equal if the hashes match.
941
942     if (is8Bit()) {
943         const LChar* searchCharacters = characters8() + index;
944
945         unsigned searchHash = 0;
946         unsigned matchHash = 0;
947         for (unsigned i = 0; i < matchLength; ++i) {
948             searchHash += searchCharacters[i];
949             matchHash += matchString[i];
950         }
951
952         unsigned i = 0;
953         while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
954             if (i == delta)
955                 return notFound;
956             searchHash += searchCharacters[i + matchLength];
957             searchHash -= searchCharacters[i];
958             ++i;
959         }
960         return index + i;
961     }
962
963     const UChar* searchCharacters = characters16() + index;
964
965     unsigned searchHash = 0;
966     unsigned matchHash = 0;
967     for (unsigned i = 0; i < matchLength; ++i) {
968         searchHash += searchCharacters[i];
969         matchHash += matchString[i];
970     }
971
972     unsigned i = 0;
973     while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
974         if (i == delta)
975             return notFound;
976         searchHash += searchCharacters[i + matchLength];
977         searchHash -= searchCharacters[i];
978         ++i;
979     }
980     return index + i;
981 }
982
983 size_t StringImpl::find(StringImpl* matchString)
984 {
985     // Check for null string to match against
986     if (UNLIKELY(!matchString))
987         return notFound;
988     unsigned matchLength = matchString->length();
989
990     // Optimization 1: fast case for strings of length 1.
991     if (matchLength == 1) {
992         if (is8Bit()) {
993             if (matchString->is8Bit())
994                 return WTF::find(characters8(), length(), matchString->characters8()[0]);
995             return WTF::find(characters8(), length(), matchString->characters16()[0]);
996         }
997         if (matchString->is8Bit())
998             return WTF::find(characters16(), length(), matchString->characters8()[0]);
999         return WTF::find(characters16(), length(), matchString->characters16()[0]);
1000     }
1001
1002     // Check matchLength is in range.
1003     if (matchLength > length())
1004         return notFound;
1005
1006     // Check for empty string to match against
1007     if (UNLIKELY(!matchLength))
1008         return 0;
1009
1010     if (is8Bit()) {
1011         if (matchString->is8Bit())
1012             return findInner(characters8(), matchString->characters8(), 0, length(), matchLength);
1013         return findInner(characters8(), matchString->characters16(), 0, length(), matchLength);
1014     }
1015
1016     if (matchString->is8Bit())
1017         return findInner(characters16(), matchString->characters8(), 0, length(), matchLength);
1018
1019     return findInner(characters16(), matchString->characters16(), 0, length(), matchLength);
1020 }
1021
1022 size_t StringImpl::find(StringImpl* matchString, unsigned index)
1023 {
1024     // Check for null or empty string to match against
1025     if (UNLIKELY(!matchString))
1026         return notFound;
1027
1028     return findCommon(*this, *matchString, index);
1029 }
1030
1031 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString) const
1032 {
1033     return ::WTF::findIgnoringASCIICase(*this, matchString, 0);
1034 }
1035
1036 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString, unsigned startOffset) const
1037 {
1038     return ::WTF::findIgnoringASCIICase(*this, matchString, startOffset);
1039 }
1040
1041 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString) const
1042 {
1043     if (!matchString)
1044         return notFound;
1045     return ::WTF::findIgnoringASCIICase(*this, *matchString, 0);
1046 }
1047
1048 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString, unsigned startOffset) const
1049 {
1050     if (!matchString)
1051         return notFound;
1052     return ::WTF::findIgnoringASCIICase(*this, *matchString, startOffset);
1053 }
1054
1055 size_t StringImpl::reverseFind(UChar character, unsigned index)
1056 {
1057     if (is8Bit())
1058         return WTF::reverseFind(characters8(), m_length, character, index);
1059     return WTF::reverseFind(characters16(), m_length, character, index);
1060 }
1061
1062 template <typename SearchCharacterType, typename MatchCharacterType>
1063 ALWAYS_INLINE static size_t reverseFindInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
1064 {
1065     // Optimization: keep a running hash of the strings,
1066     // only call equal if the hashes match.
1067
1068     // delta is the number of additional times to test; delta == 0 means test only once.
1069     unsigned delta = std::min(index, length - matchLength);
1070     
1071     unsigned searchHash = 0;
1072     unsigned matchHash = 0;
1073     for (unsigned i = 0; i < matchLength; ++i) {
1074         searchHash += searchCharacters[delta + i];
1075         matchHash += matchCharacters[i];
1076     }
1077
1078     // keep looping until we match
1079     while (searchHash != matchHash || !equal(searchCharacters + delta, matchCharacters, matchLength)) {
1080         if (!delta)
1081             return notFound;
1082         --delta;
1083         searchHash -= searchCharacters[delta + matchLength];
1084         searchHash += searchCharacters[delta];
1085     }
1086     return delta;
1087 }
1088
1089 size_t StringImpl::reverseFind(StringImpl* matchString, unsigned index)
1090 {
1091     // Check for null or empty string to match against
1092     if (!matchString)
1093         return notFound;
1094     unsigned matchLength = matchString->length();
1095     unsigned ourLength = length();
1096     if (!matchLength)
1097         return std::min(index, ourLength);
1098
1099     // Optimization 1: fast case for strings of length 1.
1100     if (matchLength == 1) {
1101         if (is8Bit())
1102             return WTF::reverseFind(characters8(), ourLength, (*matchString)[0], index);
1103         return WTF::reverseFind(characters16(), ourLength, (*matchString)[0], index);
1104     }
1105
1106     // Check index & matchLength are in range.
1107     if (matchLength > ourLength)
1108         return notFound;
1109
1110     if (is8Bit()) {
1111         if (matchString->is8Bit())
1112             return reverseFindInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1113         return reverseFindInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1114     }
1115     
1116     if (matchString->is8Bit())
1117         return reverseFindInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1118
1119     return reverseFindInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1120 }
1121
1122 ALWAYS_INLINE static bool equalInner(const StringImpl& string, unsigned startOffset, const char* matchString, unsigned matchLength)
1123 {
1124     ASSERT(matchLength <= string.length());
1125     ASSERT(startOffset + matchLength <= string.length());
1126
1127     if (string.is8Bit())
1128         return equal(string.characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1129     return equal(string.characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1130 }
1131
1132 ALWAYS_INLINE static bool equalInner(const StringImpl& string, unsigned startOffset, const StringImpl& matchString)
1133 {
1134     if (startOffset > string.length())
1135         return false;
1136     if (matchString.length() > string.length())
1137         return false;
1138     if (matchString.length() + startOffset > string.length())
1139         return false;
1140
1141     if (string.is8Bit()) {
1142         if (matchString.is8Bit())
1143             return equal(string.characters8() + startOffset, matchString.characters8(), matchString.length());
1144         return equal(string.characters8() + startOffset, matchString.characters16(), matchString.length());
1145     }
1146     if (matchString.is8Bit())
1147         return equal(string.characters16() + startOffset, matchString.characters8(), matchString.length());
1148     return equal(string.characters16() + startOffset, matchString.characters16(), matchString.length());
1149 }
1150
1151 bool StringImpl::startsWith(const StringImpl* string) const
1152 {
1153     return string && ::WTF::startsWith(*this, *string);
1154 }
1155
1156 bool StringImpl::startsWith(const StringImpl& string) const
1157 {
1158     return ::WTF::startsWith(*this, string);
1159 }
1160
1161 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl* prefix) const
1162 {
1163     return prefix && ::WTF::startsWithIgnoringASCIICase(*this, *prefix);
1164 }
1165
1166 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl& prefix) const
1167 {
1168     return ::WTF::startsWithIgnoringASCIICase(*this, prefix);
1169 }
1170
1171 bool StringImpl::startsWith(UChar character) const
1172 {
1173     return m_length && (*this)[0] == character;
1174 }
1175
1176 bool StringImpl::startsWith(const char* matchString, unsigned matchLength) const
1177 {
1178     return matchLength <= length() && equalInner(*this, 0, matchString, matchLength);
1179 }
1180
1181 bool StringImpl::hasInfixStartingAt(const StringImpl& matchString, unsigned startOffset) const
1182 {
1183     return equalInner(*this, startOffset, matchString);
1184 }
1185
1186 bool StringImpl::endsWith(StringImpl* suffix)
1187 {
1188     return suffix && ::WTF::endsWith(*this, *suffix);
1189 }
1190
1191 bool StringImpl::endsWith(StringImpl& suffix)
1192 {
1193     return ::WTF::endsWith(*this, suffix);
1194 }
1195
1196 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl* suffix) const
1197 {
1198     return suffix && ::WTF::endsWithIgnoringASCIICase(*this, *suffix);
1199 }
1200
1201 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl& suffix) const
1202 {
1203     return ::WTF::endsWithIgnoringASCIICase(*this, suffix);
1204 }
1205
1206 bool StringImpl::endsWith(UChar character) const
1207 {
1208     return m_length && (*this)[m_length - 1] == character;
1209 }
1210
1211 bool StringImpl::endsWith(const char* matchString, unsigned matchLength) const
1212 {
1213     return matchLength <= length() && equalInner(*this, length() - matchLength, matchString, matchLength);
1214 }
1215
1216 bool StringImpl::hasInfixEndingAt(const StringImpl& matchString, unsigned endOffset) const
1217 {
1218     return endOffset >= matchString.length() && equalInner(*this, endOffset - matchString.length(), matchString);
1219 }
1220
1221 Ref<StringImpl> StringImpl::replace(UChar target, UChar replacement)
1222 {
1223     if (target == replacement)
1224         return *this;
1225     unsigned i;
1226     for (i = 0; i != m_length; ++i) {
1227         UChar character = is8Bit() ? m_data8[i] : m_data16[i];
1228         if (character == target)
1229             break;
1230     }
1231     if (i == m_length)
1232         return *this;
1233
1234     if (is8Bit()) {
1235         if (target > 0xFF) {
1236             // Looking for a 16-bit character in an 8-bit string, so we're done.
1237             return *this;
1238         }
1239
1240         if (replacement <= 0xFF) {
1241             LChar* data;
1242             LChar oldChar = static_cast<LChar>(target);
1243             LChar newChar = static_cast<LChar>(replacement);
1244
1245             auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1246
1247             for (i = 0; i != m_length; ++i) {
1248                 LChar character = m_data8[i];
1249                 if (character == oldChar)
1250                     character = newChar;
1251                 data[i] = character;
1252             }
1253             return newImpl;
1254         }
1255
1256         UChar* data;
1257         auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1258
1259         for (i = 0; i != m_length; ++i) {
1260             UChar character = m_data8[i];
1261             if (character == target)
1262                 character = replacement;
1263             data[i] = character;
1264         }
1265
1266         return newImpl;
1267     }
1268
1269     UChar* data;
1270     auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1271
1272     for (i = 0; i != m_length; ++i) {
1273         UChar character = m_data16[i];
1274         if (character == target)
1275             character = replacement;
1276         data[i] = character;
1277     }
1278     return newImpl;
1279 }
1280
1281 Ref<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* string)
1282 {
1283     position = std::min(position, length());
1284     lengthToReplace = std::min(lengthToReplace, length() - position);
1285     unsigned lengthToInsert = string ? string->length() : 0;
1286     if (!lengthToReplace && !lengthToInsert)
1287         return *this;
1288
1289     if ((length() - lengthToReplace) >= (std::numeric_limits<unsigned>::max() - lengthToInsert))
1290         CRASH();
1291
1292     if (is8Bit() && (!string || string->is8Bit())) {
1293         LChar* data;
1294         auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1295         copyCharacters(data, m_data8, position);
1296         if (string)
1297             copyCharacters(data + position, string->m_data8, lengthToInsert);
1298         copyCharacters(data + position + lengthToInsert, m_data8 + position + lengthToReplace, length() - position - lengthToReplace);
1299         return newImpl;
1300     }
1301     UChar* data;
1302     auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1303     if (is8Bit())
1304         copyCharacters(data, m_data8, position);
1305     else
1306         copyCharacters(data, m_data16, position);
1307     if (string) {
1308         if (string->is8Bit())
1309             copyCharacters(data + position, string->m_data8, lengthToInsert);
1310         else
1311             copyCharacters(data + position, string->m_data16, lengthToInsert);
1312     }
1313     if (is8Bit())
1314         copyCharacters(data + position + lengthToInsert, m_data8 + position + lengthToReplace, length() - position - lengthToReplace);
1315     else
1316         copyCharacters(data + position + lengthToInsert, m_data16 + position + lengthToReplace, length() - position - lengthToReplace);
1317     return newImpl;
1318 }
1319
1320 Ref<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
1321 {
1322     if (!replacement)
1323         return *this;
1324     if (replacement->is8Bit())
1325         return replace(pattern, replacement->m_data8, replacement->length());
1326     return replace(pattern, replacement->m_data16, replacement->length());
1327 }
1328
1329 Ref<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength)
1330 {
1331     ASSERT(replacement);
1332
1333     size_t srcSegmentStart = 0;
1334     unsigned matchCount = 0;
1335
1336     // Count the matches.
1337     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1338         ++matchCount;
1339         ++srcSegmentStart;
1340     }
1341
1342     // If we have 0 matches then we don't have to do any more work.
1343     if (!matchCount)
1344         return *this;
1345
1346     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1347         CRASH();
1348
1349     unsigned replaceSize = matchCount * repStrLength;
1350     unsigned newSize = m_length - matchCount;
1351     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1352         CRASH();
1353
1354     newSize += replaceSize;
1355
1356     // Construct the new data.
1357     size_t srcSegmentEnd;
1358     unsigned srcSegmentLength;
1359     srcSegmentStart = 0;
1360     unsigned dstOffset = 0;
1361
1362     if (is8Bit()) {
1363         LChar* data;
1364         auto newImpl = createUninitialized(newSize, data);
1365
1366         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1367             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1368             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1369             dstOffset += srcSegmentLength;
1370             copyCharacters(data + dstOffset, replacement, repStrLength);
1371             dstOffset += repStrLength;
1372             srcSegmentStart = srcSegmentEnd + 1;
1373         }
1374
1375         srcSegmentLength = m_length - srcSegmentStart;
1376         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1377
1378         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1379
1380         return newImpl;
1381     }
1382
1383     UChar* data;
1384     auto newImpl = createUninitialized(newSize, data);
1385
1386     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1387         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1388         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1389
1390         dstOffset += srcSegmentLength;
1391         copyCharacters(data + dstOffset, replacement, repStrLength);
1392
1393         dstOffset += repStrLength;
1394         srcSegmentStart = srcSegmentEnd + 1;
1395     }
1396
1397     srcSegmentLength = m_length - srcSegmentStart;
1398     copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1399
1400     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1401
1402     return newImpl;
1403 }
1404
1405 Ref<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength)
1406 {
1407     ASSERT(replacement);
1408
1409     size_t srcSegmentStart = 0;
1410     unsigned matchCount = 0;
1411
1412     // Count the matches.
1413     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1414         ++matchCount;
1415         ++srcSegmentStart;
1416     }
1417
1418     // If we have 0 matches then we don't have to do any more work.
1419     if (!matchCount)
1420         return *this;
1421
1422     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1423         CRASH();
1424
1425     unsigned replaceSize = matchCount * repStrLength;
1426     unsigned newSize = m_length - matchCount;
1427     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1428         CRASH();
1429
1430     newSize += replaceSize;
1431
1432     // Construct the new data.
1433     size_t srcSegmentEnd;
1434     unsigned srcSegmentLength;
1435     srcSegmentStart = 0;
1436     unsigned dstOffset = 0;
1437
1438     if (is8Bit()) {
1439         UChar* data;
1440         auto newImpl = createUninitialized(newSize, data);
1441
1442         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1443             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1444             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1445
1446             dstOffset += srcSegmentLength;
1447             copyCharacters(data + dstOffset, replacement, repStrLength);
1448
1449             dstOffset += repStrLength;
1450             srcSegmentStart = srcSegmentEnd + 1;
1451         }
1452
1453         srcSegmentLength = m_length - srcSegmentStart;
1454         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1455
1456         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1457
1458         return newImpl;
1459     }
1460
1461     UChar* data;
1462     auto newImpl = createUninitialized(newSize, data);
1463
1464     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1465         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1466         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1467
1468         dstOffset += srcSegmentLength;
1469         copyCharacters(data + dstOffset, replacement, repStrLength);
1470
1471         dstOffset += repStrLength;
1472         srcSegmentStart = srcSegmentEnd + 1;
1473     }
1474
1475     srcSegmentLength = m_length - srcSegmentStart;
1476     copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1477
1478     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1479
1480     return newImpl;
1481 }
1482
1483 Ref<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
1484 {
1485     if (!pattern || !replacement)
1486         return *this;
1487
1488     unsigned patternLength = pattern->length();
1489     if (!patternLength)
1490         return *this;
1491         
1492     unsigned repStrLength = replacement->length();
1493     size_t srcSegmentStart = 0;
1494     unsigned matchCount = 0;
1495     
1496     // Count the matches.
1497     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1498         ++matchCount;
1499         srcSegmentStart += patternLength;
1500     }
1501     
1502     // If we have 0 matches, we don't have to do any more work
1503     if (!matchCount)
1504         return *this;
1505     
1506     unsigned newSize = m_length - matchCount * patternLength;
1507     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1508         CRASH();
1509
1510     if (newSize > (std::numeric_limits<unsigned>::max() - matchCount * repStrLength))
1511         CRASH();
1512
1513     newSize += matchCount * repStrLength;
1514
1515     
1516     // Construct the new data
1517     size_t srcSegmentEnd;
1518     unsigned srcSegmentLength;
1519     srcSegmentStart = 0;
1520     unsigned dstOffset = 0;
1521     bool srcIs8Bit = is8Bit();
1522     bool replacementIs8Bit = replacement->is8Bit();
1523     
1524     // There are 4 cases:
1525     // 1. This and replacement are both 8 bit.
1526     // 2. This and replacement are both 16 bit.
1527     // 3. This is 8 bit and replacement is 16 bit.
1528     // 4. This is 16 bit and replacement is 8 bit.
1529     if (srcIs8Bit && replacementIs8Bit) {
1530         // Case 1
1531         LChar* data;
1532         auto newImpl = createUninitialized(newSize, data);
1533         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1534             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1535             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1536             dstOffset += srcSegmentLength;
1537             copyCharacters(data + dstOffset, replacement->m_data8, repStrLength);
1538             dstOffset += repStrLength;
1539             srcSegmentStart = srcSegmentEnd + patternLength;
1540         }
1541
1542         srcSegmentLength = m_length - srcSegmentStart;
1543         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1544
1545         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1546
1547         return newImpl;
1548     }
1549
1550     UChar* data;
1551     auto newImpl = createUninitialized(newSize, data);
1552     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1553         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1554         if (srcIs8Bit) {
1555             // Case 3.
1556             copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1557         } else {
1558             // Case 2 & 4.
1559             copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1560         }
1561         dstOffset += srcSegmentLength;
1562         if (replacementIs8Bit) {
1563             // Cases 2 & 3.
1564             copyCharacters(data + dstOffset, replacement->m_data8, repStrLength);
1565         } else {
1566             // Case 4
1567             copyCharacters(data + dstOffset, replacement->m_data16, repStrLength);
1568         }
1569         dstOffset += repStrLength;
1570         srcSegmentStart = srcSegmentEnd + patternLength;
1571     }
1572
1573     srcSegmentLength = m_length - srcSegmentStart;
1574     if (srcIs8Bit) {
1575         // Case 3.
1576         copyCharacters(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength);
1577     } else {
1578         // Cases 2 & 4.
1579         copyCharacters(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength);
1580     }
1581
1582     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1583
1584     return newImpl;
1585 }
1586
1587 bool equal(const StringImpl* a, const StringImpl* b)
1588 {
1589     return equalCommon(a, b);
1590 }
1591
1592 template<typename CharacterType> inline bool equalInternal(const StringImpl* a, const CharacterType* b, unsigned length)
1593 {
1594     if (!a)
1595         return !b;
1596     if (!b)
1597         return false;
1598
1599     if (a->length() != length)
1600         return false;
1601     if (a->is8Bit())
1602         return equal(a->characters8(), b, length);
1603     return equal(a->characters16(), b, length);
1604 }
1605
1606 bool equal(const StringImpl* a, const LChar* b, unsigned length)
1607 {
1608     return equalInternal(a, b, length);
1609 }
1610
1611 bool equal(const StringImpl* a, const UChar* b, unsigned length)
1612 {
1613     return equalInternal(a, b, length);
1614 }
1615
1616 bool equal(const StringImpl* a, const LChar* b)
1617 {
1618     if (!a)
1619         return !b;
1620     if (!b)
1621         return !a;
1622
1623     unsigned length = a->length();
1624
1625     if (a->is8Bit()) {
1626         const LChar* aPtr = a->characters8();
1627         for (unsigned i = 0; i != length; ++i) {
1628             LChar bc = b[i];
1629             LChar ac = aPtr[i];
1630             if (!bc)
1631                 return false;
1632             if (ac != bc)
1633                 return false;
1634         }
1635
1636         return !b[length];
1637     }
1638
1639     const UChar* aPtr = a->characters16();
1640     for (unsigned i = 0; i != length; ++i) {
1641         LChar bc = b[i];
1642         if (!bc)
1643             return false;
1644         if (aPtr[i] != bc)
1645             return false;
1646     }
1647
1648     return !b[length];
1649 }
1650
1651 bool equal(const StringImpl& a, const StringImpl& b)
1652 {
1653     return equalCommon(a, b);
1654 }
1655
1656 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
1657 {
1658     if (!a && b && !b->length())
1659         return true;
1660     if (!b && a && !a->length())
1661         return true;
1662     return equal(a, b);
1663 }
1664
1665 bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl* b)
1666 {
1667     return a == b || (a && b && equalIgnoringASCIICase(*a, *b));
1668 }
1669
1670 bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b)
1671 {
1672     ASSERT(a);
1673     ASSERT(b);
1674     return equalIgnoringASCIICase(*a, *b);
1675 }
1676
1677 UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality)
1678 {
1679     for (unsigned i = 0; i < m_length; ++i) {
1680         auto charDirection = u_charDirection(is8Bit() ? m_data8[i] : m_data16[i]);
1681         if (charDirection == U_LEFT_TO_RIGHT) {
1682             if (hasStrongDirectionality)
1683                 *hasStrongDirectionality = true;
1684             return U_LEFT_TO_RIGHT;
1685         }
1686         if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
1687             if (hasStrongDirectionality)
1688                 *hasStrongDirectionality = true;
1689             return U_RIGHT_TO_LEFT;
1690         }
1691     }
1692     if (hasStrongDirectionality)
1693         *hasStrongDirectionality = false;
1694     return U_LEFT_TO_RIGHT;
1695 }
1696
1697 Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>&& buffer)
1698 {
1699     unsigned length = buffer.length();
1700     if (!length)
1701         return *empty();
1702     return adoptRef(*new StringImpl(buffer.release(), length));
1703 }
1704
1705 Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>&& buffer)
1706 {
1707     unsigned length = buffer.length();
1708     if (!length)
1709         return *empty();
1710     return adoptRef(*new StringImpl(buffer.release(), length));
1711 }
1712
1713 size_t StringImpl::sizeInBytes() const
1714 {
1715     // FIXME: support substrings
1716     size_t size = length();
1717     if (!is8Bit())
1718         size *= 2;
1719     return size + sizeof(*this);
1720 }
1721
1722 // Helper to write a three-byte UTF-8 code point into the buffer; caller must ensure room is available.
1723 static inline void putUTF8Triple(char*& buffer, UChar character)
1724 {
1725     ASSERT(character >= 0x0800);
1726     *buffer++ = static_cast<char>(((character >> 12) & 0x0F) | 0xE0);
1727     *buffer++ = static_cast<char>(((character >> 6) & 0x3F) | 0x80);
1728     *buffer++ = static_cast<char>((character & 0x3F) | 0x80);
1729 }
1730
1731 bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode)
1732 {
1733     if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) {
1734         const UChar* charactersEnd = characters + length;
1735         char* bufferEnd = buffer + bufferSize;
1736         while (characters < charactersEnd) {
1737             // Use strict conversion to detect unpaired surrogates.
1738             ConversionResult result = convertUTF16ToUTF8(&characters, charactersEnd, &buffer, bufferEnd, true);
1739             ASSERT(result != targetExhausted);
1740             // Conversion fails when there is an unpaired surrogate.
1741             // Put replacement character (U+FFFD) instead of the unpaired surrogate.
1742             if (result != conversionOK) {
1743                 ASSERT((0xD800 <= *characters && *characters <= 0xDFFF));
1744                 // There should be room left, since one UChar hasn't been converted.
1745                 ASSERT((buffer + 3) <= bufferEnd);
1746                 putUTF8Triple(buffer, replacementCharacter);
1747                 ++characters;
1748             }
1749         }
1750     } else {
1751         bool strict = mode == StrictConversion;
1752         const UChar* originalCharacters = characters;
1753         ConversionResult result = convertUTF16ToUTF8(&characters, characters + length, &buffer, buffer + bufferSize, strict);
1754         ASSERT(result != targetExhausted); // (length * 3) should be sufficient for any conversion
1755
1756         // Only produced from strict conversion.
1757         if (result == sourceIllegal) {
1758             ASSERT(strict);
1759             return false;
1760         }
1761
1762         // Check for an unconverted high surrogate.
1763         if (result == sourceExhausted) {
1764             if (strict)
1765                 return false;
1766             // This should be one unpaired high surrogate. Treat it the same
1767             // was as an unpaired high surrogate would have been handled in
1768             // the middle of a string with non-strict conversion - which is
1769             // to say, simply encode it to UTF-8.
1770             ASSERT_UNUSED(
1771                 originalCharacters, (characters + 1) == (originalCharacters + length));
1772             ASSERT((*characters >= 0xD800) && (*characters <= 0xDBFF));
1773             // There should be room left, since one UChar hasn't been converted.
1774             ASSERT((buffer + 3) <= (buffer + bufferSize));
1775             putUTF8Triple(buffer, *characters);
1776         }
1777     }
1778     
1779     return true;
1780 }
1781
1782 CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length)
1783 {
1784     if (!length)
1785         return CString("", 0);
1786     if (length > std::numeric_limits<unsigned>::max() / 3)
1787         return CString();
1788     Vector<char, 1024> bufferVector(length * 3);
1789     char* buffer = bufferVector.data();
1790     const LChar* source = characters;
1791     ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size());
1792     ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
1793     return CString(bufferVector.data(), buffer - bufferVector.data());
1794 }
1795
1796 CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode)
1797 {
1798     if (!length)
1799         return CString("", 0);
1800     if (length > std::numeric_limits<unsigned>::max() / 3)
1801         return CString();
1802     Vector<char, 1024> bufferVector(length * 3);
1803     char* buffer = bufferVector.data();
1804     if (!utf8Impl(characters, length, buffer, bufferVector.size(), mode))
1805         return CString();
1806     return CString(bufferVector.data(), buffer - bufferVector.data());
1807 }
1808
1809 CString StringImpl::utf8ForRange(unsigned offset, unsigned length, ConversionMode mode) const
1810 {
1811     ASSERT(offset <= this->length());
1812     ASSERT(offset + length <= this->length());
1813     
1814     if (!length)
1815         return CString("", 0);
1816
1817     // Allocate a buffer big enough to hold all the characters
1818     // (an individual UTF-16 UChar can only expand to 3 UTF-8 bytes).
1819     // Optimization ideas, if we find this function is hot:
1820     //  * We could speculatively create a CStringBuffer to contain 'length' 
1821     //    characters, and resize if necessary (i.e. if the buffer contains
1822     //    non-ascii characters). (Alternatively, scan the buffer first for
1823     //    ascii characters, so we know this will be sufficient).
1824     //  * We could allocate a CStringBuffer with an appropriate size to
1825     //    have a good chance of being able to write the string into the
1826     //    buffer without reallocing (say, 1.5 x length).
1827     if (length > std::numeric_limits<unsigned>::max() / 3)
1828         return CString();
1829     Vector<char, 1024> bufferVector(length * 3);
1830
1831     char* buffer = bufferVector.data();
1832
1833     if (is8Bit()) {
1834         const LChar* characters = this->characters8() + offset;
1835
1836         ConversionResult result = convertLatin1ToUTF8(&characters, characters + length, &buffer, buffer + bufferVector.size());
1837         ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
1838     } else {
1839         if (!utf8Impl(this->characters16() + offset, length, buffer, bufferVector.size(), mode))
1840             return CString();
1841     }
1842
1843     return CString(bufferVector.data(), buffer - bufferVector.data());
1844 }
1845
1846 CString StringImpl::utf8(ConversionMode mode) const
1847 {
1848     return utf8ForRange(0, length(), mode);
1849 }
1850
1851 NEVER_INLINE unsigned StringImpl::hashSlowCase() const
1852 {
1853     if (is8Bit())
1854         setHash(StringHasher::computeHashAndMaskTop8Bits(m_data8, m_length));
1855     else
1856         setHash(StringHasher::computeHashAndMaskTop8Bits(m_data16, m_length));
1857     return existingHash();
1858 }
1859
1860 unsigned StringImpl::concurrentHash() const
1861 {
1862     unsigned hash;
1863     if (is8Bit())
1864         hash = StringHasher::computeHashAndMaskTop8Bits(m_data8, m_length);
1865     else
1866         hash = StringHasher::computeHashAndMaskTop8Bits(m_data16, m_length);
1867     ASSERT(((hash << s_flagCount) >> s_flagCount) == hash);
1868     return hash;
1869 }
1870
1871 bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b)
1872 {
1873     if (!b)
1874         return !aLength;
1875     if (aLength != b->length())
1876         return false;
1877     if (b->is8Bit()) {
1878         const LChar* bCharacters = b->characters8();
1879         for (unsigned i = 0; i < aLength; ++i) {
1880             if (a[i] != bCharacters[i])
1881                 return false;
1882         }
1883         return true;
1884     }
1885     return !memcmp(a, b->characters16(), b->length() * sizeof(UChar));
1886 }
1887
1888 void StringImpl::releaseAssertCaged() const
1889 {
1890     if (isStatic())
1891         return;
1892     RELEASE_ASSERT(!GIGACAGE_ENABLED || Gigacage::isCaged(Gigacage::String, this));
1893     if (bufferOwnership() != BufferOwned)
1894         return;
1895     RELEASE_ASSERT(!GIGACAGE_ENABLED || Gigacage::isCaged(Gigacage::String, m_data8));
1896 }
1897
1898 } // namespace WTF