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