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