3fb94714779f72eea69ef258c6e435f4b354330e
[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, 2004, 2005, 2006, 2007, 2008, 2009, 2013-2014 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/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
105 StringImpl::~StringImpl()
106 {
107     ASSERT(!isStatic());
108
109     StringView::invalidate(*this);
110
111     STRING_STATS_REMOVE_STRING(*this);
112
113     if (isAtomic() && length() && !isSymbol())
114         AtomicStringImpl::remove(static_cast<AtomicStringImpl*>(this));
115
116     if (isSymbol() && symbolRegistry())
117         symbolRegistry()->remove(this);
118
119     BufferOwnership ownership = bufferOwnership();
120
121     if (ownership == BufferInternal)
122         return;
123     if (ownership == BufferOwned) {
124         // We use m_data8, but since it is a union with m_data16 this works either way.
125         ASSERT(m_data8);
126         fastFree(const_cast<LChar*>(m_data8));
127         return;
128     }
129
130     ASSERT(ownership == BufferSubstring);
131     ASSERT(substringBuffer());
132     substringBuffer()->deref();
133 }
134
135 void StringImpl::destroy(StringImpl* stringImpl)
136 {
137     stringImpl->~StringImpl();
138     fastFree(stringImpl);
139 }
140
141 Ref<StringImpl> StringImpl::createFromLiteral(const char* characters, unsigned length)
142 {
143     ASSERT_WITH_MESSAGE(length, "Use StringImpl::empty() to create an empty string");
144     ASSERT(charactersAreAllASCII<LChar>(reinterpret_cast<const LChar*>(characters), length));
145     return adoptRef(*new StringImpl(reinterpret_cast<const LChar*>(characters), length, ConstructWithoutCopying));
146 }
147
148 Ref<StringImpl> StringImpl::createFromLiteral(const char* characters)
149 {
150     return createFromLiteral(characters, strlen(characters));
151 }
152
153 Ref<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, unsigned length)
154 {
155     if (!length)
156         return *empty();
157
158     return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));
159 }
160
161 Ref<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, unsigned length)
162 {
163     if (!length)
164         return *empty();
165
166     return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));
167 }
168
169 template <typename CharType>
170 inline Ref<StringImpl> StringImpl::createUninitializedInternal(unsigned length, CharType*& data)
171 {
172     if (!length) {
173         data = 0;
174         return *empty();
175     }
176     return createUninitializedInternalNonEmpty(length, data);
177 }
178
179 template <typename CharType>
180 inline Ref<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsigned length, CharType*& data)
181 {
182     ASSERT(length);
183
184     // Allocate a single buffer large enough to contain the StringImpl
185     // struct as well as the data which it contains. This removes one
186     // heap allocation from this call.
187     if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharType)))
188         CRASH();
189     StringImpl* string = static_cast<StringImpl*>(fastMalloc(allocationSize<CharType>(length)));
190
191     data = string->tailPointer<CharType>();
192     return constructInternal<CharType>(string, length);
193 }
194
195 Ref<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data)
196 {
197     return createUninitializedInternal(length, data);
198 }
199
200 Ref<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data)
201 {
202     return createUninitializedInternal(length, data);
203 }
204
205 template <typename CharType>
206 inline Ref<StringImpl> StringImpl::reallocateInternal(PassRefPtr<StringImpl> originalString, unsigned length, CharType*& data)
207 {   
208     ASSERT(originalString->hasOneRef());
209     ASSERT(originalString->bufferOwnership() == BufferInternal);
210
211     if (!length) {
212         data = 0;
213         return *empty();
214     }
215
216     // Same as createUninitialized() except here we use fastRealloc.
217     if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharType)))
218         CRASH();
219
220     originalString->~StringImpl();
221     StringImpl* string = static_cast<StringImpl*>(fastRealloc(originalString.leakRef(), allocationSize<CharType>(length)));
222
223     data = string->tailPointer<CharType>();
224     return constructInternal<CharType>(string, length);
225 }
226
227 Ref<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, LChar*& data)
228 {
229     ASSERT(originalString->is8Bit());
230     return reallocateInternal(originalString, length, data);
231 }
232
233 Ref<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, UChar*& data)
234 {
235     ASSERT(!originalString->is8Bit());
236     return reallocateInternal(originalString, length, data);
237 }
238
239 template <typename CharType>
240 inline Ref<StringImpl> StringImpl::createInternal(const CharType* characters, unsigned length)
241 {
242     if (!characters || !length)
243         return *empty();
244
245     CharType* data;
246     auto string = createUninitializedInternalNonEmpty(length, data);
247     memcpy(data, characters, length * sizeof(CharType));
248     return string;
249 }
250
251 Ref<StringImpl> StringImpl::create(const UChar* characters, unsigned length)
252 {
253     return createInternal(characters, length);
254 }
255
256 Ref<StringImpl> StringImpl::create(const LChar* characters, unsigned length)
257 {
258     return createInternal(characters, length);
259 }
260
261 Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length)
262 {
263     if (!characters || !length)
264         return *empty();
265
266     LChar* data;
267     RefPtr<StringImpl> string = createUninitializedInternalNonEmpty(length, data);
268
269     for (size_t i = 0; i < length; ++i) {
270         if (characters[i] & 0xff00)
271             return create(characters, length);
272         data[i] = static_cast<LChar>(characters[i]);
273     }
274
275     return string.releaseNonNull();
276 }
277
278 Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* string)
279 {
280     return StringImpl::create8BitIfPossible(string, lengthOfNullTerminatedString(string));
281 }
282
283 Ref<StringImpl> StringImpl::create(const LChar* string)
284 {
285     if (!string)
286         return *empty();
287     size_t length = strlen(reinterpret_cast<const char*>(string));
288     if (length > std::numeric_limits<unsigned>::max())
289         CRASH();
290     return create(string, length);
291 }
292
293 Ref<StringImpl> StringImpl::createSymbol(PassRefPtr<StringImpl> rep)
294 {
295     StringImpl* ownerRep = (rep->bufferOwnership() == BufferSubstring) ? rep->substringBuffer() : rep.get();
296
297     // We allocate a buffer that contains
298     // 1. the StringImpl struct
299     // 2. the pointer to the owner string
300     // 3. the pointer to the symbol registry
301     // 4. the placeholder for symbol aware hash value (allocated size is pointer size, but only 4 bytes are used)
302     StringImpl* stringImpl = static_cast<StringImpl*>(fastMalloc(allocationSize<StringImpl*>(3)));
303     if (rep->is8Bit())
304         return adoptRef(*new (NotNull, stringImpl) StringImpl(CreateSymbol, rep->m_data8, rep->length(), ownerRep));
305     return adoptRef(*new (NotNull, stringImpl) StringImpl(CreateSymbol, rep->m_data16, rep->length(), ownerRep));
306 }
307
308 Ref<StringImpl> StringImpl::createSymbolEmpty()
309 {
310     return createSymbol(empty());
311 }
312
313 bool StringImpl::containsOnlyWhitespace()
314 {
315     // FIXME: The definition of whitespace here includes a number of characters
316     // that are not whitespace from the point of view of RenderText; I wonder if
317     // that's a problem in practice.
318     if (is8Bit()) {
319         for (unsigned i = 0; i < m_length; ++i) {
320             UChar c = m_data8[i];
321             if (!isASCIISpace(c))
322                 return false;
323         }
324
325         return true;
326     }
327
328     for (unsigned i = 0; i < m_length; ++i) {
329         UChar c = m_data16[i];
330         if (!isASCIISpace(c))
331             return false;
332     }
333     return true;
334 }
335
336 Ref<StringImpl> StringImpl::substring(unsigned start, unsigned length)
337 {
338     if (start >= m_length)
339         return *empty();
340     unsigned maxLength = m_length - start;
341     if (length >= maxLength) {
342         if (!start)
343             return *this;
344         length = maxLength;
345     }
346     if (is8Bit())
347         return create(m_data8 + start, length);
348
349     return create(m_data16 + start, length);
350 }
351
352 UChar32 StringImpl::characterStartingAt(unsigned i)
353 {
354     if (is8Bit())
355         return m_data8[i];
356     if (U16_IS_SINGLE(m_data16[i]))
357         return m_data16[i];
358     if (i + 1 < m_length && U16_IS_LEAD(m_data16[i]) && U16_IS_TRAIL(m_data16[i + 1]))
359         return U16_GET_SUPPLEMENTARY(m_data16[i], m_data16[i + 1]);
360     return 0;
361 }
362
363 Ref<StringImpl> StringImpl::lower()
364 {
365     // Note: This is a hot function in the Dromaeo benchmark, specifically the
366     // no-op code path up through the first 'return' statement.
367
368     // First scan the string for uppercase and non-ASCII characters:
369     if (is8Bit()) {
370         unsigned failingIndex;
371         for (unsigned i = 0; i < m_length; ++i) {
372             LChar character = m_data8[i];
373             if (UNLIKELY((character & ~0x7F) || isASCIIUpper(character))) {
374                 failingIndex = i;
375                 goto SlowPath;
376             }
377         }
378         return *this;
379
380 SlowPath:
381         LChar* data8;
382         auto newImpl = createUninitializedInternalNonEmpty(m_length, data8);
383
384         for (unsigned i = 0; i < failingIndex; ++i)
385             data8[i] = m_data8[i];
386
387         for (unsigned i = failingIndex; i < m_length; ++i) {
388             LChar character = m_data8[i];
389             if (!(character & ~0x7F))
390                 data8[i] = toASCIILower(character);
391             else {
392                 ASSERT(u_tolower(character) <= 0xFF);
393                 data8[i] = static_cast<LChar>(u_tolower(character));
394             }
395         }
396
397         return newImpl;
398     }
399     bool noUpper = true;
400     unsigned ored = 0;
401
402     for (unsigned i = 0; i < m_length; ++i) {
403         UChar character = m_data16[i];
404         if (UNLIKELY(isASCIIUpper(character)))
405             noUpper = false;
406         ored |= character;
407     }
408     // Nothing to do if the string is all ASCII with no uppercase.
409     if (noUpper && !(ored & ~0x7F))
410         return *this;
411
412     if (!(ored & ~0x7F)) {
413         UChar* data16;
414         auto newImpl = createUninitializedInternalNonEmpty(m_length, data16);
415         
416         for (unsigned i = 0; i < m_length; ++i) {
417             UChar c = m_data16[i];
418             data16[i] = toASCIILower(c);
419         }
420         return newImpl;
421     }
422
423     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
424         CRASH();
425     int32_t length = m_length;
426
427     // Do a slower implementation for cases that include non-ASCII characters.
428     UChar* data16;
429     RefPtr<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data16);
430
431     UErrorCode status = U_ZERO_ERROR;
432     int32_t realLength = u_strToLower(data16, length, m_data16, m_length, "", &status);
433     if (U_SUCCESS(status) && realLength == length)
434         return newImpl.releaseNonNull();
435
436     newImpl = createUninitialized(realLength, data16);
437     status = U_ZERO_ERROR;
438     u_strToLower(data16, realLength, m_data16, m_length, "", &status);
439     if (U_FAILURE(status))
440         return *this;
441     return newImpl.releaseNonNull();
442 }
443
444 Ref<StringImpl> StringImpl::upper()
445 {
446     // This function could be optimized for no-op cases the way lower() is,
447     // but in empirical testing, few actual calls to upper() are no-ops, so
448     // it wouldn't be worth the extra time for pre-scanning.
449
450     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
451         CRASH();
452     int32_t length = m_length;
453
454     if (is8Bit()) {
455         LChar* data8;
456         RefPtr<StringImpl> newImpl = createUninitialized(m_length, data8);
457         
458         // Do a faster loop for the case where all the characters are ASCII.
459         unsigned ored = 0;
460         for (int i = 0; i < length; ++i) {
461             LChar c = m_data8[i];
462             ored |= c;
463 #if CPU(X86) && defined(_MSC_VER) && _MSC_VER >=1700
464             // Workaround for an MSVC 2012 x86 optimizer bug. Remove once the bug is fixed.
465             // See https://connect.microsoft.com/VisualStudio/feedback/details/780362/optimization-bug-of-range-comparison
466             // for more details.
467             data8[i] = c >= 'a' && c <= 'z' ? c & ~0x20 : c;
468 #else
469             data8[i] = toASCIIUpper(c);
470 #endif
471         }
472         if (!(ored & ~0x7F))
473             return newImpl.releaseNonNull();
474
475         // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
476         int numberSharpSCharacters = 0;
477
478         // There are two special cases.
479         //  1. latin-1 characters when converted to upper case are 16 bit characters.
480         //  2. Lower case sharp-S converts to "SS" (two characters)
481         for (int32_t i = 0; i < length; ++i) {
482             LChar c = m_data8[i];
483             if (UNLIKELY(c == smallLetterSharpS))
484                 ++numberSharpSCharacters;
485             ASSERT(u_toupper(c) <= 0xFFFF);
486             UChar upper = u_toupper(c);
487             if (UNLIKELY(upper > 0xff)) {
488                 // Since this upper-cased character does not fit in an 8-bit string, we need to take the 16-bit path.
489                 goto upconvert;
490             }
491             data8[i] = static_cast<LChar>(upper);
492         }
493
494         if (!numberSharpSCharacters)
495             return newImpl.releaseNonNull();
496
497         // We have numberSSCharacters sharp-s characters, but none of the other special characters.
498         newImpl = createUninitialized(m_length + numberSharpSCharacters, data8);
499
500         LChar* dest = data8;
501
502         for (int32_t i = 0; i < length; ++i) {
503             LChar c = m_data8[i];
504             if (c == smallLetterSharpS) {
505                 *dest++ = 'S';
506                 *dest++ = 'S';
507             } else {
508                 ASSERT(u_toupper(c) <= 0xFF);
509                 *dest++ = static_cast<LChar>(u_toupper(c));
510             }
511         }
512
513         return newImpl.releaseNonNull();
514     }
515
516 upconvert:
517     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
518     const UChar* source16 = upconvertedCharacters;
519
520     UChar* data16;
521     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data16);
522     
523     // Do a faster loop for the case where all the characters are ASCII.
524     unsigned ored = 0;
525     for (int i = 0; i < length; ++i) {
526         UChar c = source16[i];
527         ored |= c;
528         data16[i] = toASCIIUpper(c);
529     }
530     if (!(ored & ~0x7F))
531         return newImpl.releaseNonNull();
532
533     // Do a slower implementation for cases that include non-ASCII characters.
534     UErrorCode status = U_ZERO_ERROR;
535     int32_t realLength = u_strToUpper(data16, length, source16, m_length, "", &status);
536     if (U_SUCCESS(status) && realLength == length)
537         return newImpl.releaseNonNull();
538     newImpl = createUninitialized(realLength, data16);
539     status = U_ZERO_ERROR;
540     u_strToUpper(data16, realLength, source16, m_length, "", &status);
541     if (U_FAILURE(status))
542         return *this;
543     return newImpl.releaseNonNull();
544 }
545
546 static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier)
547 {
548     // Either "tr" or "az" locale, with case sensitive comparison and allowing for an ignored subtag.
549     UChar first = localeIdentifier[0];
550     UChar second = localeIdentifier[1];
551     return ((isASCIIAlphaCaselessEqual(first, 't') && isASCIIAlphaCaselessEqual(second, 'r'))
552         || (isASCIIAlphaCaselessEqual(first, 'a') && isASCIIAlphaCaselessEqual(second, 'z')))
553         && (localeIdentifier.length() == 2 || localeIdentifier[2] == '-');
554 }
555
556 Ref<StringImpl> StringImpl::lower(const AtomicString& localeIdentifier)
557 {
558     // Use the more-optimized code path most of the time.
559     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules.
560     // FIXME: Could possibly optimize further by looking for the specific sequences
561     // that have locale-specific lowercasing. There are only three of them.
562     if (!needsTurkishCasingRules(localeIdentifier))
563         return lower();
564
565     // FIXME: Could share more code with the main StringImpl::lower by factoring out
566     // this last part into a shared function that takes a locale string, since this is
567     // just like the end of that function.
568
569     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
570         CRASH();
571     int length = m_length;
572
573     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
574     // allocating memory just to turn localeIdentifier into a C string, and we assume
575     // there is no difference between the uppercasing for "tr" and "az" locales.
576     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
577     const UChar* source16 = upconvertedCharacters;
578     UChar* data16;
579     RefPtr<StringImpl> newString = createUninitialized(length, data16);
580     UErrorCode status = U_ZERO_ERROR;
581     int realLength = u_strToLower(data16, length, source16, length, "tr", &status);
582     if (U_SUCCESS(status) && realLength == length)
583         return newString.releaseNonNull();
584     newString = createUninitialized(realLength, data16);
585     status = U_ZERO_ERROR;
586     u_strToLower(data16, realLength, source16, length, "tr", &status);
587     if (U_FAILURE(status))
588         return *this;
589     return newString.releaseNonNull();
590 }
591
592 Ref<StringImpl> StringImpl::upper(const AtomicString& localeIdentifier)
593 {
594     // Use the more-optimized code path most of the time.
595     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules,
596     // and that the only affected character is lowercase "i".
597     if (!needsTurkishCasingRules(localeIdentifier) || find('i') == notFound)
598         return upper();
599
600     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
601         CRASH();
602     int length = m_length;
603
604     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
605     // allocating memory just to turn localeIdentifier into a C string, and we assume
606     // there is no difference between the uppercasing for "tr" and "az" locales.
607     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
608     const UChar* source16 = upconvertedCharacters;
609     UChar* data16;
610     RefPtr<StringImpl> newString = createUninitialized(length, data16);
611     UErrorCode status = U_ZERO_ERROR;
612     int realLength = u_strToUpper(data16, length, source16, length, "tr", &status);
613     if (U_SUCCESS(status) && realLength == length)
614         return newString.releaseNonNull();
615     newString = createUninitialized(realLength, data16);
616     status = U_ZERO_ERROR;
617     u_strToUpper(data16, realLength, source16, length, "tr", &status);
618     if (U_FAILURE(status))
619         return *this;
620     return newString.releaseNonNull();
621 }
622
623 Ref<StringImpl> StringImpl::foldCase()
624 {
625     // FIXME: Why doesn't this function have a preflight like the one in StringImpl::lower?
626
627     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
628         CRASH();
629     int32_t length = m_length;
630
631     if (is8Bit()) {
632         // Do a faster loop for the case where all the characters are ASCII.
633         LChar* data;
634         auto newImpl = createUninitialized(m_length, data);
635         LChar ored = 0;
636
637         for (int32_t i = 0; i < length; ++i) {
638             LChar c = m_data8[i];
639             data[i] = toASCIILower(c);
640             ored |= c;
641         }
642
643         if (!(ored & ~0x7F))
644             return newImpl;
645
646         // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
647         // FIXME: Shouldn't this use u_foldCase instead of u_tolower?
648         for (int32_t i = 0; i < length; ++i) {
649             ASSERT(u_tolower(m_data8[i]) <= 0xFF);
650             data[i] = static_cast<LChar>(u_tolower(m_data8[i]));
651         }
652
653         return newImpl;
654     }
655
656     // Do a faster loop for the case where all the characters are ASCII.
657     UChar* data;
658     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
659     UChar ored = 0;
660     for (int32_t i = 0; i < length; ++i) {
661         UChar c = m_data16[i];
662         ored |= c;
663         data[i] = toASCIILower(c);
664     }
665     if (!(ored & ~0x7F))
666         return newImpl.releaseNonNull();
667
668     // Do a slower implementation for cases that include non-ASCII characters.
669     UErrorCode status = U_ZERO_ERROR;
670     int32_t realLength = u_strFoldCase(data, length, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);
671     if (U_SUCCESS(status) && realLength == length)
672         return newImpl.releaseNonNull();
673     newImpl = createUninitialized(realLength, data);
674     status = U_ZERO_ERROR;
675     u_strFoldCase(data, realLength, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);
676     if (U_FAILURE(status))
677         return *this;
678     return newImpl.releaseNonNull();
679 }
680
681 Ref<StringImpl> StringImpl::convertToASCIILowercase()
682 {
683     if (is8Bit()) {
684         unsigned failingIndex;
685         for (unsigned i = 0; i < m_length; ++i) {
686             LChar character = m_data8[i];
687             if (UNLIKELY(isASCIIUpper(character))) {
688                 failingIndex = i;
689                 goto SlowPath;
690             }
691         }
692         return *this;
693
694 SlowPath:
695         LChar* data8;
696         Ref<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data8);
697         for (unsigned i = 0; i < failingIndex; ++i)
698             data8[i] = m_data8[i];
699         for (unsigned i = failingIndex; i < m_length; ++i)
700             data8[i] = toASCIILower(m_data8[i]);
701         return newImpl;
702     }
703
704     bool noUpper = true;
705     for (unsigned i = 0; i < m_length; ++i) {
706         if (UNLIKELY(isASCIIUpper(m_data16[i])))
707             noUpper = false;
708     }
709     if (noUpper)
710         return *this;
711
712     UChar* data16;
713     Ref<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data16);
714     for (unsigned i = 0; i < m_length; ++i)
715         data16[i] = toASCIILower(m_data16[i]);
716     return newImpl;
717 }
718
719 template <class UCharPredicate>
720 inline Ref<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate)
721 {
722     if (!m_length)
723         return *this;
724
725     unsigned start = 0;
726     unsigned end = m_length - 1;
727     
728     // skip white space from start
729     while (start <= end && predicate(is8Bit() ? m_data8[start] : m_data16[start]))
730         ++start;
731     
732     // only white space
733     if (start > end) 
734         return *empty();
735
736     // skip white space from end
737     while (end && predicate(is8Bit() ? m_data8[end] : m_data16[end]))
738         --end;
739
740     if (!start && end == m_length - 1)
741         return *this;
742     if (is8Bit())
743         return create(m_data8 + start, end + 1 - start);
744     return create(m_data16 + start, end + 1 - start);
745 }
746
747 class UCharPredicate {
748 public:
749     inline UCharPredicate(CharacterMatchFunctionPtr function): m_function(function) { }
750
751     inline bool operator()(UChar ch) const
752     {
753         return m_function(ch);
754     }
755
756 private:
757     const CharacterMatchFunctionPtr m_function;
758 };
759
760 class SpaceOrNewlinePredicate {
761 public:
762     inline bool operator()(UChar ch) const
763     {
764         return isSpaceOrNewline(ch);
765     }
766 };
767
768 Ref<StringImpl> StringImpl::stripWhiteSpace()
769 {
770     return stripMatchedCharacters(SpaceOrNewlinePredicate());
771 }
772
773 Ref<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
774 {
775     return stripMatchedCharacters(UCharPredicate(isWhiteSpace));
776 }
777
778 template <typename CharType>
779 ALWAYS_INLINE Ref<StringImpl> StringImpl::removeCharacters(const CharType* characters, CharacterMatchFunctionPtr findMatch)
780 {
781     const CharType* from = characters;
782     const CharType* fromend = from + m_length;
783     
784     // Assume the common case will not remove any characters
785     while (from != fromend && !findMatch(*from))
786         ++from;
787     if (from == fromend)
788         return *this;
789     
790     StringBuffer<CharType> data(m_length);
791     CharType* to = data.characters();
792     unsigned outc = from - characters;
793     
794     if (outc)
795         memcpy(to, characters, outc * sizeof(CharType));
796
797     while (true) {
798         while (from != fromend && findMatch(*from))
799             ++from;
800         while (from != fromend && !findMatch(*from))
801             to[outc++] = *from++;
802         if (from == fromend)
803             break;
804     }
805
806     data.shrink(outc);
807
808     return adopt(data);
809 }
810
811 Ref<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)
812 {
813     if (is8Bit())
814         return removeCharacters(characters8(), findMatch);
815     return removeCharacters(characters16(), findMatch);
816 }
817
818 template <typename CharType, class UCharPredicate>
819 inline Ref<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate)
820 {
821     StringBuffer<CharType> data(m_length);
822
823     const CharType* from = characters<CharType>();
824     const CharType* fromend = from + m_length;
825     int outc = 0;
826     bool changedToSpace = false;
827     
828     CharType* to = data.characters();
829     
830     while (true) {
831         while (from != fromend && predicate(*from)) {
832             if (*from != ' ')
833                 changedToSpace = true;
834             ++from;
835         }
836         while (from != fromend && !predicate(*from))
837             to[outc++] = *from++;
838         if (from != fromend)
839             to[outc++] = ' ';
840         else
841             break;
842     }
843     
844     if (outc > 0 && to[outc - 1] == ' ')
845         --outc;
846     
847     if (static_cast<unsigned>(outc) == m_length && !changedToSpace)
848         return *this;
849     
850     data.shrink(outc);
851     
852     return adopt(data);
853 }
854
855 Ref<StringImpl> StringImpl::simplifyWhiteSpace()
856 {
857     if (is8Bit())
858         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate());
859     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate());
860 }
861
862 Ref<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
863 {
864     if (is8Bit())
865         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(UCharPredicate(isWhiteSpace));
866     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(UCharPredicate(isWhiteSpace));
867 }
868
869 int StringImpl::toIntStrict(bool* ok, int base)
870 {
871     if (is8Bit())
872         return charactersToIntStrict(characters8(), m_length, ok, base);
873     return charactersToIntStrict(characters16(), m_length, ok, base);
874 }
875
876 unsigned StringImpl::toUIntStrict(bool* ok, int base)
877 {
878     if (is8Bit())
879         return charactersToUIntStrict(characters8(), m_length, ok, base);
880     return charactersToUIntStrict(characters16(), m_length, ok, base);
881 }
882
883 int64_t StringImpl::toInt64Strict(bool* ok, int base)
884 {
885     if (is8Bit())
886         return charactersToInt64Strict(characters8(), m_length, ok, base);
887     return charactersToInt64Strict(characters16(), m_length, ok, base);
888 }
889
890 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)
891 {
892     if (is8Bit())
893         return charactersToUInt64Strict(characters8(), m_length, ok, base);
894     return charactersToUInt64Strict(characters16(), m_length, ok, base);
895 }
896
897 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)
898 {
899     if (is8Bit())
900         return charactersToIntPtrStrict(characters8(), m_length, ok, base);
901     return charactersToIntPtrStrict(characters16(), m_length, ok, base);
902 }
903
904 int StringImpl::toInt(bool* ok)
905 {
906     if (is8Bit())
907         return charactersToInt(characters8(), m_length, ok);
908     return charactersToInt(characters16(), m_length, ok);
909 }
910
911 unsigned StringImpl::toUInt(bool* ok)
912 {
913     if (is8Bit())
914         return charactersToUInt(characters8(), m_length, ok);
915     return charactersToUInt(characters16(), m_length, ok);
916 }
917
918 int64_t StringImpl::toInt64(bool* ok)
919 {
920     if (is8Bit())
921         return charactersToInt64(characters8(), m_length, ok);
922     return charactersToInt64(characters16(), m_length, ok);
923 }
924
925 uint64_t StringImpl::toUInt64(bool* ok)
926 {
927     if (is8Bit())
928         return charactersToUInt64(characters8(), m_length, ok);
929     return charactersToUInt64(characters16(), m_length, ok);
930 }
931
932 intptr_t StringImpl::toIntPtr(bool* ok)
933 {
934     if (is8Bit())
935         return charactersToIntPtr(characters8(), m_length, ok);
936     return charactersToIntPtr(characters16(), m_length, ok);
937 }
938
939 double StringImpl::toDouble(bool* ok)
940 {
941     if (is8Bit())
942         return charactersToDouble(characters8(), m_length, ok);
943     return charactersToDouble(characters16(), m_length, ok);
944 }
945
946 float StringImpl::toFloat(bool* ok)
947 {
948     if (is8Bit())
949         return charactersToFloat(characters8(), m_length, ok);
950     return charactersToFloat(characters16(), m_length, ok);
951 }
952
953 bool equalIgnoringCase(const LChar* a, const LChar* b, unsigned length)
954 {
955     while (length--) {
956         if (StringImpl::latin1CaseFoldTable[*a++] != StringImpl::latin1CaseFoldTable[*b++])
957             return false;
958     }
959     return true;
960 }
961
962 bool equalIgnoringCase(const UChar* a, const LChar* b, unsigned length)
963 {
964     while (length--) {
965         if (u_foldCase(*a++, U_FOLD_CASE_DEFAULT) != StringImpl::latin1CaseFoldTable[*b++])
966             return false;
967     }
968     return true;
969 }
970
971 size_t StringImpl::find(CharacterMatchFunctionPtr matchFunction, unsigned start)
972 {
973     if (is8Bit())
974         return WTF::find(characters8(), m_length, matchFunction, start);
975     return WTF::find(characters16(), m_length, matchFunction, start);
976 }
977
978 size_t StringImpl::find(const LChar* matchString, unsigned index)
979 {
980     // Check for null or empty string to match against
981     if (!matchString)
982         return notFound;
983     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
984     if (matchStringLength > std::numeric_limits<unsigned>::max())
985         CRASH();
986     unsigned matchLength = matchStringLength;
987     if (!matchLength)
988         return std::min(index, length());
989
990     // Optimization 1: fast case for strings of length 1.
991     if (matchLength == 1) {
992         if (is8Bit())
993             return WTF::find(characters8(), length(), matchString[0], index);
994         return WTF::find(characters16(), length(), *matchString, index);
995     }
996
997     // Check index & matchLength are in range.
998     if (index > length())
999         return notFound;
1000     unsigned searchLength = length() - index;
1001     if (matchLength > searchLength)
1002         return notFound;
1003     // delta is the number of additional times to test; delta == 0 means test only once.
1004     unsigned delta = searchLength - matchLength;
1005
1006     // Optimization 2: keep a running hash of the strings,
1007     // only call equal if the hashes match.
1008
1009     if (is8Bit()) {
1010         const LChar* searchCharacters = characters8() + index;
1011
1012         unsigned searchHash = 0;
1013         unsigned matchHash = 0;
1014         for (unsigned i = 0; i < matchLength; ++i) {
1015             searchHash += searchCharacters[i];
1016             matchHash += matchString[i];
1017         }
1018
1019         unsigned i = 0;
1020         while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
1021             if (i == delta)
1022                 return notFound;
1023             searchHash += searchCharacters[i + matchLength];
1024             searchHash -= searchCharacters[i];
1025             ++i;
1026         }
1027         return index + i;
1028     }
1029
1030     const UChar* searchCharacters = characters16() + index;
1031
1032     unsigned searchHash = 0;
1033     unsigned matchHash = 0;
1034     for (unsigned i = 0; i < matchLength; ++i) {
1035         searchHash += searchCharacters[i];
1036         matchHash += matchString[i];
1037     }
1038
1039     unsigned i = 0;
1040     while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
1041         if (i == delta)
1042             return notFound;
1043         searchHash += searchCharacters[i + matchLength];
1044         searchHash -= searchCharacters[i];
1045         ++i;
1046     }
1047     return index + i;
1048 }
1049
1050 size_t StringImpl::findIgnoringCase(const LChar* matchString, unsigned index)
1051 {
1052     // Check for null or empty string to match against
1053     if (!matchString)
1054         return notFound;
1055     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
1056     if (matchStringLength > std::numeric_limits<unsigned>::max())
1057         CRASH();
1058     unsigned matchLength = matchStringLength;
1059     if (!matchLength)
1060         return std::min(index, length());
1061
1062     // Check index & matchLength are in range.
1063     if (index > length())
1064         return notFound;
1065     unsigned searchLength = length() - index;
1066     if (matchLength > searchLength)
1067         return notFound;
1068     // delta is the number of additional times to test; delta == 0 means test only once.
1069     unsigned delta = searchLength - matchLength;
1070
1071     if (is8Bit()) {
1072         const LChar* searchCharacters = characters8() + index;
1073
1074         unsigned i = 0;
1075         while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) {
1076             if (i == delta)
1077                 return notFound;
1078             ++i;
1079         }
1080         return index + i;
1081     }
1082
1083     const UChar* searchCharacters = characters16() + index;
1084
1085     unsigned i = 0;
1086     while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) {
1087         if (i == delta)
1088             return notFound;
1089         ++i;
1090     }
1091     return index + i;
1092 }
1093
1094 template <typename SearchCharacterType, typename MatchCharacterType>
1095 ALWAYS_INLINE static size_t findInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
1096 {
1097     // Optimization: keep a running hash of the strings,
1098     // only call equal() if the hashes match.
1099
1100     // delta is the number of additional times to test; delta == 0 means test only once.
1101     unsigned delta = searchLength - matchLength;
1102
1103     unsigned searchHash = 0;
1104     unsigned matchHash = 0;
1105
1106     for (unsigned i = 0; i < matchLength; ++i) {
1107         searchHash += searchCharacters[i];
1108         matchHash += matchCharacters[i];
1109     }
1110
1111     unsigned i = 0;
1112     // keep looping until we match
1113     while (searchHash != matchHash || !equal(searchCharacters + i, matchCharacters, matchLength)) {
1114         if (i == delta)
1115             return notFound;
1116         searchHash += searchCharacters[i + matchLength];
1117         searchHash -= searchCharacters[i];
1118         ++i;
1119     }
1120     return index + i;        
1121 }
1122
1123 size_t StringImpl::find(StringImpl* matchString)
1124 {
1125     // Check for null string to match against
1126     if (UNLIKELY(!matchString))
1127         return notFound;
1128     unsigned matchLength = matchString->length();
1129
1130     // Optimization 1: fast case for strings of length 1.
1131     if (matchLength == 1) {
1132         if (is8Bit()) {
1133             if (matchString->is8Bit())
1134                 return WTF::find(characters8(), length(), matchString->characters8()[0]);
1135             return WTF::find(characters8(), length(), matchString->characters16()[0]);
1136         }
1137         if (matchString->is8Bit())
1138             return WTF::find(characters16(), length(), matchString->characters8()[0]);
1139         return WTF::find(characters16(), length(), matchString->characters16()[0]);
1140     }
1141
1142     // Check matchLength is in range.
1143     if (matchLength > length())
1144         return notFound;
1145
1146     // Check for empty string to match against
1147     if (UNLIKELY(!matchLength))
1148         return 0;
1149
1150     if (is8Bit()) {
1151         if (matchString->is8Bit())
1152             return findInner(characters8(), matchString->characters8(), 0, length(), matchLength);
1153         return findInner(characters8(), matchString->characters16(), 0, length(), matchLength);
1154     }
1155
1156     if (matchString->is8Bit())
1157         return findInner(characters16(), matchString->characters8(), 0, length(), matchLength);
1158
1159     return findInner(characters16(), matchString->characters16(), 0, length(), matchLength);
1160 }
1161
1162 size_t StringImpl::find(StringImpl* matchString, unsigned index)
1163 {
1164     // Check for null or empty string to match against
1165     if (UNLIKELY(!matchString))
1166         return notFound;
1167
1168     unsigned matchLength = matchString->length();
1169
1170     // Optimization 1: fast case for strings of length 1.
1171     if (matchLength == 1) {
1172         if (is8Bit())
1173             return WTF::find(characters8(), length(), (*matchString)[0], index);
1174         return WTF::find(characters16(), length(), (*matchString)[0], index);
1175     }
1176
1177     if (UNLIKELY(!matchLength))
1178         return std::min(index, length());
1179
1180     // Check index & matchLength are in range.
1181     if (index > length())
1182         return notFound;
1183     unsigned searchLength = length() - index;
1184     if (matchLength > searchLength)
1185         return notFound;
1186
1187     if (is8Bit()) {
1188         if (matchString->is8Bit())
1189             return findInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
1190         return findInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
1191     }
1192
1193     if (matchString->is8Bit())
1194         return findInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength);
1195
1196     return findInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
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 (!equalIgnoringCase(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 (!equalIgnoringCase(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 equalIgnoringCase(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1395     return equalIgnoringCase(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 equalIgnoringCase(const StringImpl* a, const StringImpl* b)
1969 {
1970     if (a == b)
1971         return true;
1972     if (!a || !b)
1973         return false;
1974
1975     return CaseFoldingHash::equal(a, b);
1976 }
1977
1978 bool equalIgnoringCase(const StringImpl* a, const LChar* b)
1979 {
1980     if (!a)
1981         return !b;
1982     if (!b)
1983         return !a;
1984
1985     unsigned length = a->length();
1986
1987     // Do a faster loop for the case where all the characters are ASCII.
1988     UChar ored = 0;
1989     bool equal = true;
1990     if (a->is8Bit()) {
1991         const LChar* as = a->characters8();
1992         for (unsigned i = 0; i != length; ++i) {
1993             LChar bc = b[i];
1994             if (!bc)
1995                 return false;
1996             UChar ac = as[i];
1997             ored |= ac;
1998             equal = equal && (toASCIILower(ac) == toASCIILower(bc));
1999         }
2000         
2001         // Do a slower implementation for cases that include non-ASCII characters.
2002         if (ored & ~0x7F) {
2003             equal = true;
2004             for (unsigned i = 0; i != length; ++i)
2005                 equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
2006         }
2007         
2008         return equal && !b[length];        
2009     }
2010
2011     const UChar* as = a->characters16();
2012     for (unsigned i = 0; i != length; ++i) {
2013         LChar bc = b[i];
2014         if (!bc)
2015             return false;
2016         UChar ac = as[i];
2017         ored |= ac;
2018         equal = equal && (toASCIILower(ac) == toASCIILower(bc));
2019     }
2020
2021     // Do a slower implementation for cases that include non-ASCII characters.
2022     if (ored & ~0x7F) {
2023         equal = true;
2024         for (unsigned i = 0; i != length; ++i) {
2025             equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
2026         }
2027     }
2028
2029     return equal && !b[length];
2030 }
2031
2032 bool equalIgnoringCaseNonNull(const StringImpl* a, const StringImpl* b)
2033 {
2034     ASSERT(a && b);
2035     if (a == b)
2036         return true;
2037
2038     unsigned length = a->length();
2039     if (length != b->length())
2040         return false;
2041
2042     if (a->is8Bit()) {
2043         if (b->is8Bit())
2044             return equalIgnoringCase(a->characters8(), b->characters8(), length);
2045
2046         return equalIgnoringCase(b->characters16(), a->characters8(), length);
2047     }
2048
2049     if (b->is8Bit())
2050         return equalIgnoringCase(a->characters16(), b->characters8(), length);
2051
2052     return equalIgnoringCase(a->characters16(), b->characters16(), length);
2053 }
2054
2055 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
2056 {
2057     if (!a && b && !b->length())
2058         return true;
2059     if (!b && a && !a->length())
2060         return true;
2061     return equal(a, b);
2062 }
2063
2064 bool equalIgnoringASCIICase(const StringImpl& a, const StringImpl& b)
2065 {
2066     return equalIgnoringASCIICaseCommon(a, b);
2067 }
2068
2069 bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl*b)
2070 {
2071     if (a == b)
2072         return true;
2073     if (!a || !b)
2074         return false;
2075     return equalIgnoringASCIICaseCommon(*a, *b);
2076 }
2077
2078 bool equalIgnoringASCIICase(const StringImpl& a, const char* b, unsigned bLength)
2079 {
2080     if (bLength != a.length())
2081         return false;
2082
2083     if (a.is8Bit())
2084         return equalIgnoringASCIICase(a.characters8(), b, bLength);
2085
2086     return equalIgnoringASCIICase(a.characters16(), b, bLength);
2087 }
2088
2089 bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b)
2090 {
2091     ASSERT(a);
2092     ASSERT(b);
2093     return equalIgnoringASCIICaseCommon(*a, *b);
2094 }
2095
2096 UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality)
2097 {
2098     for (unsigned i = 0; i < m_length; ++i) {
2099         UCharDirection charDirection = u_charDirection(is8Bit() ? m_data8[i] : m_data16[i]);
2100         if (charDirection == U_LEFT_TO_RIGHT) {
2101             if (hasStrongDirectionality)
2102                 *hasStrongDirectionality = true;
2103             return U_LEFT_TO_RIGHT;
2104         }
2105         if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
2106             if (hasStrongDirectionality)
2107                 *hasStrongDirectionality = true;
2108             return U_RIGHT_TO_LEFT;
2109         }
2110     }
2111     if (hasStrongDirectionality)
2112         *hasStrongDirectionality = false;
2113     return U_LEFT_TO_RIGHT;
2114 }
2115
2116 Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>& buffer)
2117 {
2118     unsigned length = buffer.length();
2119     if (!length)
2120         return *empty();
2121     return adoptRef(*new StringImpl(buffer.release(), length));
2122 }
2123
2124 Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>& buffer)
2125 {
2126     unsigned length = buffer.length();
2127     if (!length)
2128         return *empty();
2129     return adoptRef(*new StringImpl(buffer.release(), length));
2130 }
2131
2132 size_t StringImpl::sizeInBytes() const
2133 {
2134     // FIXME: support substrings
2135     size_t size = length();
2136     if (!is8Bit())
2137         size *= 2;
2138     return size + sizeof(*this);
2139 }
2140
2141 // Helper to write a three-byte UTF-8 code point to the buffer, caller must check room is available.
2142 static inline void putUTF8Triple(char*& buffer, UChar ch)
2143 {
2144     ASSERT(ch >= 0x0800);
2145     *buffer++ = static_cast<char>(((ch >> 12) & 0x0F) | 0xE0);
2146     *buffer++ = static_cast<char>(((ch >> 6) & 0x3F) | 0x80);
2147     *buffer++ = static_cast<char>((ch & 0x3F) | 0x80);
2148 }
2149
2150 bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode)
2151 {
2152     if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) {
2153         const UChar* charactersEnd = characters + length;
2154         char* bufferEnd = buffer + bufferSize;
2155         while (characters < charactersEnd) {
2156             // Use strict conversion to detect unpaired surrogates.
2157             ConversionResult result = convertUTF16ToUTF8(&characters, charactersEnd, &buffer, bufferEnd, true);
2158             ASSERT(result != targetExhausted);
2159             // Conversion fails when there is an unpaired surrogate.
2160             // Put replacement character (U+FFFD) instead of the unpaired surrogate.
2161             if (result != conversionOK) {
2162                 ASSERT((0xD800 <= *characters && *characters <= 0xDFFF));
2163                 // There should be room left, since one UChar hasn't been converted.
2164                 ASSERT((buffer + 3) <= bufferEnd);
2165                 putUTF8Triple(buffer, replacementCharacter);
2166                 ++characters;
2167             }
2168         }
2169     } else {
2170         bool strict = mode == StrictConversion;
2171         const UChar* originalCharacters = characters;
2172         ConversionResult result = convertUTF16ToUTF8(&characters, characters + length, &buffer, buffer + bufferSize, strict);
2173         ASSERT(result != targetExhausted); // (length * 3) should be sufficient for any conversion
2174
2175         // Only produced from strict conversion.
2176         if (result == sourceIllegal) {
2177             ASSERT(strict);
2178             return false;
2179         }
2180
2181         // Check for an unconverted high surrogate.
2182         if (result == sourceExhausted) {
2183             if (strict)
2184                 return false;
2185             // This should be one unpaired high surrogate. Treat it the same
2186             // was as an unpaired high surrogate would have been handled in
2187             // the middle of a string with non-strict conversion - which is
2188             // to say, simply encode it to UTF-8.
2189             ASSERT_UNUSED(
2190                 originalCharacters, (characters + 1) == (originalCharacters + length));
2191             ASSERT((*characters >= 0xD800) && (*characters <= 0xDBFF));
2192             // There should be room left, since one UChar hasn't been converted.
2193             ASSERT((buffer + 3) <= (buffer + bufferSize));
2194             putUTF8Triple(buffer, *characters);
2195         }
2196     }
2197     
2198     return true;
2199 }
2200
2201 CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length)
2202 {
2203     if (!length)
2204         return CString("", 0);
2205     if (length > std::numeric_limits<unsigned>::max() / 3)
2206         return CString();
2207     Vector<char, 1024> bufferVector(length * 3);
2208     char* buffer = bufferVector.data();
2209     const LChar* source = characters;
2210     ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size());
2211     ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2212     return CString(bufferVector.data(), buffer - bufferVector.data());
2213 }
2214
2215 CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode)
2216 {
2217     if (!length)
2218         return CString("", 0);
2219     if (length > std::numeric_limits<unsigned>::max() / 3)
2220         return CString();
2221     Vector<char, 1024> bufferVector(length * 3);
2222     char* buffer = bufferVector.data();
2223     if (!utf8Impl(characters, length, buffer, bufferVector.size(), mode))
2224         return CString();
2225     return CString(bufferVector.data(), buffer - bufferVector.data());
2226 }
2227
2228 CString StringImpl::utf8ForRange(unsigned offset, unsigned length, ConversionMode mode) const
2229 {
2230     ASSERT(offset <= this->length());
2231     ASSERT(offset + length <= this->length());
2232     
2233     if (!length)
2234         return CString("", 0);
2235
2236     // Allocate a buffer big enough to hold all the characters
2237     // (an individual UTF-16 UChar can only expand to 3 UTF-8 bytes).
2238     // Optimization ideas, if we find this function is hot:
2239     //  * We could speculatively create a CStringBuffer to contain 'length' 
2240     //    characters, and resize if necessary (i.e. if the buffer contains
2241     //    non-ascii characters). (Alternatively, scan the buffer first for
2242     //    ascii characters, so we know this will be sufficient).
2243     //  * We could allocate a CStringBuffer with an appropriate size to
2244     //    have a good chance of being able to write the string into the
2245     //    buffer without reallocing (say, 1.5 x length).
2246     if (length > std::numeric_limits<unsigned>::max() / 3)
2247         return CString();
2248     Vector<char, 1024> bufferVector(length * 3);
2249
2250     char* buffer = bufferVector.data();
2251
2252     if (is8Bit()) {
2253         const LChar* characters = this->characters8() + offset;
2254
2255         ConversionResult result = convertLatin1ToUTF8(&characters, characters + length, &buffer, buffer + bufferVector.size());
2256         ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2257     } else {
2258         if (!utf8Impl(this->characters16() + offset, length, buffer, bufferVector.size(), mode))
2259             return CString();
2260     }
2261
2262     return CString(bufferVector.data(), buffer - bufferVector.data());
2263 }
2264
2265 CString StringImpl::utf8(ConversionMode mode) const
2266 {
2267     return utf8ForRange(0, length(), mode);
2268 }
2269
2270 // Table is based on ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
2271 const UChar StringImpl::latin1CaseFoldTable[256] = {
2272     0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
2273     0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, 
2274     0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, 
2275     0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f,
2276     0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2277     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f,
2278     0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2279     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f,
2280     0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f,
2281     0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f,
2282     0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, 0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af,
2283     0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x03bc, 0x00b6, 0x00b7, 0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf,
2284     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2285     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00d7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00df,
2286     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2287     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff, 
2288 };
2289
2290 bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b)
2291 {
2292     if (!b)
2293         return !aLength;
2294     if (aLength != b->length())
2295         return false;
2296     if (b->is8Bit()) {
2297         const LChar* bCharacters = b->characters8();
2298         for (unsigned i = 0; i < aLength; ++i) {
2299             if (a[i] != bCharacters[i])
2300                 return false;
2301         }
2302         return true;
2303     }
2304     return !memcmp(a, b->characters16(), b->length() * sizeof(UChar));
2305 }
2306
2307 } // namespace WTF