Introduce UniquedStringImpl and SymbolImpl to separate symbolic strings from AtomicSt...
[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/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::createSymbolEmpty()
310 {
311     return createSymbol(empty());
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::lower()
365 {
366     // Note: This is 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::upper()
446 {
447     // This function could be optimized for no-op cases the way lower() is,
448     // but in empirical testing, few actual calls to upper() are no-ops, so
449     // it wouldn't be worth the extra time for pre-scanning.
450
451     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
452         CRASH();
453     int32_t length = m_length;
454
455     if (is8Bit()) {
456         LChar* data8;
457         RefPtr<StringImpl> newImpl = createUninitialized(m_length, data8);
458         
459         // Do a faster loop for the case where all the characters are ASCII.
460         unsigned ored = 0;
461         for (int i = 0; i < length; ++i) {
462             LChar c = m_data8[i];
463             ored |= c;
464 #if CPU(X86) && defined(_MSC_VER) && _MSC_VER >=1700
465             // Workaround for an MSVC 2012 x86 optimizer bug. Remove once the bug is fixed.
466             // See https://connect.microsoft.com/VisualStudio/feedback/details/780362/optimization-bug-of-range-comparison
467             // for more details.
468             data8[i] = c >= 'a' && c <= 'z' ? c & ~0x20 : c;
469 #else
470             data8[i] = toASCIIUpper(c);
471 #endif
472         }
473         if (!(ored & ~0x7F))
474             return newImpl.releaseNonNull();
475
476         // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
477         int numberSharpSCharacters = 0;
478
479         // There are two special cases.
480         //  1. latin-1 characters when converted to upper case are 16 bit characters.
481         //  2. Lower case sharp-S converts to "SS" (two characters)
482         for (int32_t i = 0; i < length; ++i) {
483             LChar c = m_data8[i];
484             if (UNLIKELY(c == smallLetterSharpS))
485                 ++numberSharpSCharacters;
486             ASSERT(u_toupper(c) <= 0xFFFF);
487             UChar upper = u_toupper(c);
488             if (UNLIKELY(upper > 0xff)) {
489                 // Since this upper-cased character does not fit in an 8-bit string, we need to take the 16-bit path.
490                 goto upconvert;
491             }
492             data8[i] = static_cast<LChar>(upper);
493         }
494
495         if (!numberSharpSCharacters)
496             return newImpl.releaseNonNull();
497
498         // We have numberSSCharacters sharp-s characters, but none of the other special characters.
499         newImpl = createUninitialized(m_length + numberSharpSCharacters, data8);
500
501         LChar* dest = data8;
502
503         for (int32_t i = 0; i < length; ++i) {
504             LChar c = m_data8[i];
505             if (c == smallLetterSharpS) {
506                 *dest++ = 'S';
507                 *dest++ = 'S';
508             } else {
509                 ASSERT(u_toupper(c) <= 0xFF);
510                 *dest++ = static_cast<LChar>(u_toupper(c));
511             }
512         }
513
514         return newImpl.releaseNonNull();
515     }
516
517 upconvert:
518     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
519     const UChar* source16 = upconvertedCharacters;
520
521     UChar* data16;
522     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data16);
523     
524     // Do a faster loop for the case where all the characters are ASCII.
525     unsigned ored = 0;
526     for (int i = 0; i < length; ++i) {
527         UChar c = source16[i];
528         ored |= c;
529         data16[i] = toASCIIUpper(c);
530     }
531     if (!(ored & ~0x7F))
532         return newImpl.releaseNonNull();
533
534     // Do a slower implementation for cases that include non-ASCII characters.
535     UErrorCode status = U_ZERO_ERROR;
536     int32_t realLength = u_strToUpper(data16, length, source16, m_length, "", &status);
537     if (U_SUCCESS(status) && realLength == length)
538         return newImpl.releaseNonNull();
539     newImpl = createUninitialized(realLength, data16);
540     status = U_ZERO_ERROR;
541     u_strToUpper(data16, realLength, source16, m_length, "", &status);
542     if (U_FAILURE(status))
543         return *this;
544     return newImpl.releaseNonNull();
545 }
546
547 static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier)
548 {
549     // Either "tr" or "az" locale, with case sensitive comparison and allowing for an ignored subtag.
550     UChar first = localeIdentifier[0];
551     UChar second = localeIdentifier[1];
552     return ((isASCIIAlphaCaselessEqual(first, 't') && isASCIIAlphaCaselessEqual(second, 'r'))
553         || (isASCIIAlphaCaselessEqual(first, 'a') && isASCIIAlphaCaselessEqual(second, 'z')))
554         && (localeIdentifier.length() == 2 || localeIdentifier[2] == '-');
555 }
556
557 Ref<StringImpl> StringImpl::lower(const AtomicString& localeIdentifier)
558 {
559     // Use the more-optimized code path most of the time.
560     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules.
561     // FIXME: Could possibly optimize further by looking for the specific sequences
562     // that have locale-specific lowercasing. There are only three of them.
563     if (!needsTurkishCasingRules(localeIdentifier))
564         return lower();
565
566     // FIXME: Could share more code with the main StringImpl::lower by factoring out
567     // this last part into a shared function that takes a locale string, since this is
568     // just like the end of that function.
569
570     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
571         CRASH();
572     int length = m_length;
573
574     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
575     // allocating memory just to turn localeIdentifier into a C string, and we assume
576     // there is no difference between the uppercasing for "tr" and "az" locales.
577     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
578     const UChar* source16 = upconvertedCharacters;
579     UChar* data16;
580     RefPtr<StringImpl> newString = createUninitialized(length, data16);
581     UErrorCode status = U_ZERO_ERROR;
582     int realLength = u_strToLower(data16, length, source16, length, "tr", &status);
583     if (U_SUCCESS(status) && realLength == length)
584         return newString.releaseNonNull();
585     newString = createUninitialized(realLength, data16);
586     status = U_ZERO_ERROR;
587     u_strToLower(data16, realLength, source16, length, "tr", &status);
588     if (U_FAILURE(status))
589         return *this;
590     return newString.releaseNonNull();
591 }
592
593 Ref<StringImpl> StringImpl::upper(const AtomicString& localeIdentifier)
594 {
595     // Use the more-optimized code path most of the time.
596     // Assuming here that the only locale-specific lowercasing is the Turkish casing rules,
597     // and that the only affected character is lowercase "i".
598     if (!needsTurkishCasingRules(localeIdentifier) || find('i') == notFound)
599         return upper();
600
601     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
602         CRASH();
603     int length = m_length;
604
605     // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than
606     // allocating memory just to turn localeIdentifier into a C string, and we assume
607     // there is no difference between the uppercasing for "tr" and "az" locales.
608     auto upconvertedCharacters = StringView(*this).upconvertedCharacters();
609     const UChar* source16 = upconvertedCharacters;
610     UChar* data16;
611     RefPtr<StringImpl> newString = createUninitialized(length, data16);
612     UErrorCode status = U_ZERO_ERROR;
613     int realLength = u_strToUpper(data16, length, source16, length, "tr", &status);
614     if (U_SUCCESS(status) && realLength == length)
615         return newString.releaseNonNull();
616     newString = createUninitialized(realLength, data16);
617     status = U_ZERO_ERROR;
618     u_strToUpper(data16, realLength, source16, length, "tr", &status);
619     if (U_FAILURE(status))
620         return *this;
621     return newString.releaseNonNull();
622 }
623
624 Ref<StringImpl> StringImpl::foldCase()
625 {
626     // FIXME: Why doesn't this function have a preflight like the one in StringImpl::lower?
627
628     if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max()))
629         CRASH();
630     int32_t length = m_length;
631
632     if (is8Bit()) {
633         // Do a faster loop for the case where all the characters are ASCII.
634         LChar* data;
635         auto newImpl = createUninitialized(m_length, data);
636         LChar ored = 0;
637
638         for (int32_t i = 0; i < length; ++i) {
639             LChar c = m_data8[i];
640             data[i] = toASCIILower(c);
641             ored |= c;
642         }
643
644         if (!(ored & ~0x7F))
645             return newImpl;
646
647         // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
648         // FIXME: Shouldn't this use u_foldCase instead of u_tolower?
649         for (int32_t i = 0; i < length; ++i) {
650             ASSERT(u_tolower(m_data8[i]) <= 0xFF);
651             data[i] = static_cast<LChar>(u_tolower(m_data8[i]));
652         }
653
654         return newImpl;
655     }
656
657     // Do a faster loop for the case where all the characters are ASCII.
658     UChar* data;
659     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
660     UChar ored = 0;
661     for (int32_t i = 0; i < length; ++i) {
662         UChar c = m_data16[i];
663         ored |= c;
664         data[i] = toASCIILower(c);
665     }
666     if (!(ored & ~0x7F))
667         return newImpl.releaseNonNull();
668
669     // Do a slower implementation for cases that include non-ASCII characters.
670     UErrorCode status = U_ZERO_ERROR;
671     int32_t realLength = u_strFoldCase(data, length, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);
672     if (U_SUCCESS(status) && realLength == length)
673         return newImpl.releaseNonNull();
674     newImpl = createUninitialized(realLength, data);
675     status = U_ZERO_ERROR;
676     u_strFoldCase(data, realLength, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);
677     if (U_FAILURE(status))
678         return *this;
679     return newImpl.releaseNonNull();
680 }
681
682 Ref<StringImpl> StringImpl::convertToASCIILowercase()
683 {
684     if (is8Bit()) {
685         unsigned failingIndex;
686         for (unsigned i = 0; i < m_length; ++i) {
687             LChar character = m_data8[i];
688             if (UNLIKELY(isASCIIUpper(character))) {
689                 failingIndex = i;
690                 goto SlowPath;
691             }
692         }
693         return *this;
694
695 SlowPath:
696         LChar* data8;
697         Ref<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data8);
698         for (unsigned i = 0; i < failingIndex; ++i)
699             data8[i] = m_data8[i];
700         for (unsigned i = failingIndex; i < m_length; ++i)
701             data8[i] = toASCIILower(m_data8[i]);
702         return newImpl;
703     }
704
705     bool noUpper = true;
706     for (unsigned i = 0; i < m_length; ++i) {
707         if (UNLIKELY(isASCIIUpper(m_data16[i])))
708             noUpper = false;
709     }
710     if (noUpper)
711         return *this;
712
713     UChar* data16;
714     Ref<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data16);
715     for (unsigned i = 0; i < m_length; ++i)
716         data16[i] = toASCIILower(m_data16[i]);
717     return newImpl;
718 }
719
720 template <class UCharPredicate>
721 inline Ref<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate)
722 {
723     if (!m_length)
724         return *this;
725
726     unsigned start = 0;
727     unsigned end = m_length - 1;
728     
729     // skip white space from start
730     while (start <= end && predicate(is8Bit() ? m_data8[start] : m_data16[start]))
731         ++start;
732     
733     // only white space
734     if (start > end) 
735         return *empty();
736
737     // skip white space from end
738     while (end && predicate(is8Bit() ? m_data8[end] : m_data16[end]))
739         --end;
740
741     if (!start && end == m_length - 1)
742         return *this;
743     if (is8Bit())
744         return create(m_data8 + start, end + 1 - start);
745     return create(m_data16 + start, end + 1 - start);
746 }
747
748 class UCharPredicate {
749 public:
750     inline UCharPredicate(CharacterMatchFunctionPtr function): m_function(function) { }
751
752     inline bool operator()(UChar ch) const
753     {
754         return m_function(ch);
755     }
756
757 private:
758     const CharacterMatchFunctionPtr m_function;
759 };
760
761 class SpaceOrNewlinePredicate {
762 public:
763     inline bool operator()(UChar ch) const
764     {
765         return isSpaceOrNewline(ch);
766     }
767 };
768
769 Ref<StringImpl> StringImpl::stripWhiteSpace()
770 {
771     return stripMatchedCharacters(SpaceOrNewlinePredicate());
772 }
773
774 Ref<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
775 {
776     return stripMatchedCharacters(UCharPredicate(isWhiteSpace));
777 }
778
779 template <typename CharType>
780 ALWAYS_INLINE Ref<StringImpl> StringImpl::removeCharacters(const CharType* characters, CharacterMatchFunctionPtr findMatch)
781 {
782     const CharType* from = characters;
783     const CharType* fromend = from + m_length;
784     
785     // Assume the common case will not remove any characters
786     while (from != fromend && !findMatch(*from))
787         ++from;
788     if (from == fromend)
789         return *this;
790     
791     StringBuffer<CharType> data(m_length);
792     CharType* to = data.characters();
793     unsigned outc = from - characters;
794     
795     if (outc)
796         memcpy(to, characters, outc * sizeof(CharType));
797
798     while (true) {
799         while (from != fromend && findMatch(*from))
800             ++from;
801         while (from != fromend && !findMatch(*from))
802             to[outc++] = *from++;
803         if (from == fromend)
804             break;
805     }
806
807     data.shrink(outc);
808
809     return adopt(data);
810 }
811
812 Ref<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)
813 {
814     if (is8Bit())
815         return removeCharacters(characters8(), findMatch);
816     return removeCharacters(characters16(), findMatch);
817 }
818
819 template <typename CharType, class UCharPredicate>
820 inline Ref<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate)
821 {
822     StringBuffer<CharType> data(m_length);
823
824     const CharType* from = characters<CharType>();
825     const CharType* fromend = from + m_length;
826     int outc = 0;
827     bool changedToSpace = false;
828     
829     CharType* to = data.characters();
830     
831     while (true) {
832         while (from != fromend && predicate(*from)) {
833             if (*from != ' ')
834                 changedToSpace = true;
835             ++from;
836         }
837         while (from != fromend && !predicate(*from))
838             to[outc++] = *from++;
839         if (from != fromend)
840             to[outc++] = ' ';
841         else
842             break;
843     }
844     
845     if (outc > 0 && to[outc - 1] == ' ')
846         --outc;
847     
848     if (static_cast<unsigned>(outc) == m_length && !changedToSpace)
849         return *this;
850     
851     data.shrink(outc);
852     
853     return adopt(data);
854 }
855
856 Ref<StringImpl> StringImpl::simplifyWhiteSpace()
857 {
858     if (is8Bit())
859         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate());
860     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate());
861 }
862
863 Ref<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
864 {
865     if (is8Bit())
866         return StringImpl::simplifyMatchedCharactersToSpace<LChar>(UCharPredicate(isWhiteSpace));
867     return StringImpl::simplifyMatchedCharactersToSpace<UChar>(UCharPredicate(isWhiteSpace));
868 }
869
870 int StringImpl::toIntStrict(bool* ok, int base)
871 {
872     if (is8Bit())
873         return charactersToIntStrict(characters8(), m_length, ok, base);
874     return charactersToIntStrict(characters16(), m_length, ok, base);
875 }
876
877 unsigned StringImpl::toUIntStrict(bool* ok, int base)
878 {
879     if (is8Bit())
880         return charactersToUIntStrict(characters8(), m_length, ok, base);
881     return charactersToUIntStrict(characters16(), m_length, ok, base);
882 }
883
884 int64_t StringImpl::toInt64Strict(bool* ok, int base)
885 {
886     if (is8Bit())
887         return charactersToInt64Strict(characters8(), m_length, ok, base);
888     return charactersToInt64Strict(characters16(), m_length, ok, base);
889 }
890
891 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)
892 {
893     if (is8Bit())
894         return charactersToUInt64Strict(characters8(), m_length, ok, base);
895     return charactersToUInt64Strict(characters16(), m_length, ok, base);
896 }
897
898 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)
899 {
900     if (is8Bit())
901         return charactersToIntPtrStrict(characters8(), m_length, ok, base);
902     return charactersToIntPtrStrict(characters16(), m_length, ok, base);
903 }
904
905 int StringImpl::toInt(bool* ok)
906 {
907     if (is8Bit())
908         return charactersToInt(characters8(), m_length, ok);
909     return charactersToInt(characters16(), m_length, ok);
910 }
911
912 unsigned StringImpl::toUInt(bool* ok)
913 {
914     if (is8Bit())
915         return charactersToUInt(characters8(), m_length, ok);
916     return charactersToUInt(characters16(), m_length, ok);
917 }
918
919 int64_t StringImpl::toInt64(bool* ok)
920 {
921     if (is8Bit())
922         return charactersToInt64(characters8(), m_length, ok);
923     return charactersToInt64(characters16(), m_length, ok);
924 }
925
926 uint64_t StringImpl::toUInt64(bool* ok)
927 {
928     if (is8Bit())
929         return charactersToUInt64(characters8(), m_length, ok);
930     return charactersToUInt64(characters16(), m_length, ok);
931 }
932
933 intptr_t StringImpl::toIntPtr(bool* ok)
934 {
935     if (is8Bit())
936         return charactersToIntPtr(characters8(), m_length, ok);
937     return charactersToIntPtr(characters16(), m_length, ok);
938 }
939
940 double StringImpl::toDouble(bool* ok)
941 {
942     if (is8Bit())
943         return charactersToDouble(characters8(), m_length, ok);
944     return charactersToDouble(characters16(), m_length, ok);
945 }
946
947 float StringImpl::toFloat(bool* ok)
948 {
949     if (is8Bit())
950         return charactersToFloat(characters8(), m_length, ok);
951     return charactersToFloat(characters16(), m_length, ok);
952 }
953
954 bool equalIgnoringCase(const LChar* a, const LChar* b, unsigned length)
955 {
956     while (length--) {
957         if (StringImpl::latin1CaseFoldTable[*a++] != StringImpl::latin1CaseFoldTable[*b++])
958             return false;
959     }
960     return true;
961 }
962
963 bool equalIgnoringCase(const UChar* a, const LChar* b, unsigned length)
964 {
965     while (length--) {
966         if (u_foldCase(*a++, U_FOLD_CASE_DEFAULT) != StringImpl::latin1CaseFoldTable[*b++])
967             return false;
968     }
969     return true;
970 }
971
972 size_t StringImpl::find(CharacterMatchFunctionPtr matchFunction, unsigned start)
973 {
974     if (is8Bit())
975         return WTF::find(characters8(), m_length, matchFunction, start);
976     return WTF::find(characters16(), m_length, matchFunction, start);
977 }
978
979 size_t StringImpl::find(const LChar* matchString, unsigned index)
980 {
981     // Check for null or empty string to match against
982     if (!matchString)
983         return notFound;
984     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
985     if (matchStringLength > std::numeric_limits<unsigned>::max())
986         CRASH();
987     unsigned matchLength = matchStringLength;
988     if (!matchLength)
989         return std::min(index, length());
990
991     // Optimization 1: fast case for strings of length 1.
992     if (matchLength == 1) {
993         if (is8Bit())
994             return WTF::find(characters8(), length(), matchString[0], index);
995         return WTF::find(characters16(), length(), *matchString, index);
996     }
997
998     // Check index & matchLength are in range.
999     if (index > length())
1000         return notFound;
1001     unsigned searchLength = length() - index;
1002     if (matchLength > searchLength)
1003         return notFound;
1004     // delta is the number of additional times to test; delta == 0 means test only once.
1005     unsigned delta = searchLength - matchLength;
1006
1007     // Optimization 2: keep a running hash of the strings,
1008     // only call equal if the hashes match.
1009
1010     if (is8Bit()) {
1011         const LChar* searchCharacters = characters8() + index;
1012
1013         unsigned searchHash = 0;
1014         unsigned matchHash = 0;
1015         for (unsigned i = 0; i < matchLength; ++i) {
1016             searchHash += searchCharacters[i];
1017             matchHash += matchString[i];
1018         }
1019
1020         unsigned i = 0;
1021         while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
1022             if (i == delta)
1023                 return notFound;
1024             searchHash += searchCharacters[i + matchLength];
1025             searchHash -= searchCharacters[i];
1026             ++i;
1027         }
1028         return index + i;
1029     }
1030
1031     const UChar* searchCharacters = characters16() + index;
1032
1033     unsigned searchHash = 0;
1034     unsigned matchHash = 0;
1035     for (unsigned i = 0; i < matchLength; ++i) {
1036         searchHash += searchCharacters[i];
1037         matchHash += matchString[i];
1038     }
1039
1040     unsigned i = 0;
1041     while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
1042         if (i == delta)
1043             return notFound;
1044         searchHash += searchCharacters[i + matchLength];
1045         searchHash -= searchCharacters[i];
1046         ++i;
1047     }
1048     return index + i;
1049 }
1050
1051 size_t StringImpl::findIgnoringCase(const LChar* matchString, unsigned index)
1052 {
1053     // Check for null or empty string to match against
1054     if (!matchString)
1055         return notFound;
1056     size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
1057     if (matchStringLength > std::numeric_limits<unsigned>::max())
1058         CRASH();
1059     unsigned matchLength = matchStringLength;
1060     if (!matchLength)
1061         return std::min(index, length());
1062
1063     // Check index & matchLength are in range.
1064     if (index > length())
1065         return notFound;
1066     unsigned searchLength = length() - index;
1067     if (matchLength > searchLength)
1068         return notFound;
1069     // delta is the number of additional times to test; delta == 0 means test only once.
1070     unsigned delta = searchLength - matchLength;
1071
1072     if (is8Bit()) {
1073         const LChar* searchCharacters = characters8() + index;
1074
1075         unsigned i = 0;
1076         while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) {
1077             if (i == delta)
1078                 return notFound;
1079             ++i;
1080         }
1081         return index + i;
1082     }
1083
1084     const UChar* searchCharacters = characters16() + index;
1085
1086     unsigned i = 0;
1087     while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) {
1088         if (i == delta)
1089             return notFound;
1090         ++i;
1091     }
1092     return index + i;
1093 }
1094
1095 template <typename SearchCharacterType, typename MatchCharacterType>
1096 ALWAYS_INLINE static size_t findInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
1097 {
1098     // Optimization: keep a running hash of the strings,
1099     // only call equal() if the hashes match.
1100
1101     // delta is the number of additional times to test; delta == 0 means test only once.
1102     unsigned delta = searchLength - matchLength;
1103
1104     unsigned searchHash = 0;
1105     unsigned matchHash = 0;
1106
1107     for (unsigned i = 0; i < matchLength; ++i) {
1108         searchHash += searchCharacters[i];
1109         matchHash += matchCharacters[i];
1110     }
1111
1112     unsigned i = 0;
1113     // keep looping until we match
1114     while (searchHash != matchHash || !equal(searchCharacters + i, matchCharacters, matchLength)) {
1115         if (i == delta)
1116             return notFound;
1117         searchHash += searchCharacters[i + matchLength];
1118         searchHash -= searchCharacters[i];
1119         ++i;
1120     }
1121     return index + i;        
1122 }
1123
1124 size_t StringImpl::find(StringImpl* matchString)
1125 {
1126     // Check for null string to match against
1127     if (UNLIKELY(!matchString))
1128         return notFound;
1129     unsigned matchLength = matchString->length();
1130
1131     // Optimization 1: fast case for strings of length 1.
1132     if (matchLength == 1) {
1133         if (is8Bit()) {
1134             if (matchString->is8Bit())
1135                 return WTF::find(characters8(), length(), matchString->characters8()[0]);
1136             return WTF::find(characters8(), length(), matchString->characters16()[0]);
1137         }
1138         if (matchString->is8Bit())
1139             return WTF::find(characters16(), length(), matchString->characters8()[0]);
1140         return WTF::find(characters16(), length(), matchString->characters16()[0]);
1141     }
1142
1143     // Check matchLength is in range.
1144     if (matchLength > length())
1145         return notFound;
1146
1147     // Check for empty string to match against
1148     if (UNLIKELY(!matchLength))
1149         return 0;
1150
1151     if (is8Bit()) {
1152         if (matchString->is8Bit())
1153             return findInner(characters8(), matchString->characters8(), 0, length(), matchLength);
1154         return findInner(characters8(), matchString->characters16(), 0, length(), matchLength);
1155     }
1156
1157     if (matchString->is8Bit())
1158         return findInner(characters16(), matchString->characters8(), 0, length(), matchLength);
1159
1160     return findInner(characters16(), matchString->characters16(), 0, length(), matchLength);
1161 }
1162
1163 size_t StringImpl::find(StringImpl* matchString, unsigned index)
1164 {
1165     // Check for null or empty string to match against
1166     if (UNLIKELY(!matchString))
1167         return notFound;
1168
1169     unsigned matchLength = matchString->length();
1170
1171     // Optimization 1: fast case for strings of length 1.
1172     if (matchLength == 1) {
1173         if (is8Bit())
1174             return WTF::find(characters8(), length(), (*matchString)[0], index);
1175         return WTF::find(characters16(), length(), (*matchString)[0], index);
1176     }
1177
1178     if (UNLIKELY(!matchLength))
1179         return std::min(index, length());
1180
1181     // Check index & matchLength are in range.
1182     if (index > length())
1183         return notFound;
1184     unsigned searchLength = length() - index;
1185     if (matchLength > searchLength)
1186         return notFound;
1187
1188     if (is8Bit()) {
1189         if (matchString->is8Bit())
1190             return findInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
1191         return findInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
1192     }
1193
1194     if (matchString->is8Bit())
1195         return findInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength);
1196
1197     return findInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
1198 }
1199
1200 template <typename SearchCharacterType, typename MatchCharacterType>
1201 ALWAYS_INLINE static size_t findIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
1202 {
1203     // delta is the number of additional times to test; delta == 0 means test only once.
1204     unsigned delta = searchLength - matchLength;
1205
1206     unsigned i = 0;
1207     // keep looping until we match
1208     while (!equalIgnoringCase(searchCharacters + i, matchCharacters, matchLength)) {
1209         if (i == delta)
1210             return notFound;
1211         ++i;
1212     }
1213     return index + i;
1214 }
1215
1216 size_t StringImpl::findIgnoringCase(StringImpl* matchString, unsigned index)
1217 {
1218     // Check for null or empty string to match against
1219     if (!matchString)
1220         return notFound;
1221     unsigned matchLength = matchString->length();
1222     if (!matchLength)
1223         return std::min(index, length());
1224
1225     // Check index & matchLength are in range.
1226     if (index > length())
1227         return notFound;
1228     unsigned searchLength = length() - index;
1229     if (matchLength > searchLength)
1230         return notFound;
1231
1232     if (is8Bit()) {
1233         if (matchString->is8Bit())
1234             return findIgnoringCaseInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
1235         return findIgnoringCaseInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
1236     }
1237
1238     if (matchString->is8Bit())
1239         return findIgnoringCaseInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength);
1240
1241     return findIgnoringCaseInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
1242 }
1243
1244 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString) const
1245 {
1246     return ::WTF::findIgnoringASCIICase(*this, matchString, 0);
1247 }
1248
1249 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString, unsigned startOffset) const
1250 {
1251     return ::WTF::findIgnoringASCIICase(*this, matchString, startOffset);
1252 }
1253
1254 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString) const
1255 {
1256     if (!matchString)
1257         return notFound;
1258     return ::WTF::findIgnoringASCIICase(*this, *matchString, 0);
1259 }
1260
1261 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString, unsigned startOffset) const
1262 {
1263     if (!matchString)
1264         return notFound;
1265     return ::WTF::findIgnoringASCIICase(*this, *matchString, startOffset);
1266 }
1267
1268 size_t StringImpl::findNextLineStart(unsigned index)
1269 {
1270     if (is8Bit())
1271         return WTF::findNextLineStart(characters8(), m_length, index);
1272     return WTF::findNextLineStart(characters16(), m_length, index);
1273 }
1274
1275 size_t StringImpl::reverseFind(UChar c, unsigned index)
1276 {
1277     if (is8Bit())
1278         return WTF::reverseFind(characters8(), m_length, c, index);
1279     return WTF::reverseFind(characters16(), m_length, c, index);
1280 }
1281
1282 template <typename SearchCharacterType, typename MatchCharacterType>
1283 ALWAYS_INLINE static size_t reverseFindInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
1284 {
1285     // Optimization: keep a running hash of the strings,
1286     // only call equal if the hashes match.
1287
1288     // delta is the number of additional times to test; delta == 0 means test only once.
1289     unsigned delta = std::min(index, length - matchLength);
1290     
1291     unsigned searchHash = 0;
1292     unsigned matchHash = 0;
1293     for (unsigned i = 0; i < matchLength; ++i) {
1294         searchHash += searchCharacters[delta + i];
1295         matchHash += matchCharacters[i];
1296     }
1297
1298     // keep looping until we match
1299     while (searchHash != matchHash || !equal(searchCharacters + delta, matchCharacters, matchLength)) {
1300         if (!delta)
1301             return notFound;
1302         --delta;
1303         searchHash -= searchCharacters[delta + matchLength];
1304         searchHash += searchCharacters[delta];
1305     }
1306     return delta;
1307 }
1308
1309 size_t StringImpl::reverseFind(StringImpl* matchString, unsigned index)
1310 {
1311     // Check for null or empty string to match against
1312     if (!matchString)
1313         return notFound;
1314     unsigned matchLength = matchString->length();
1315     unsigned ourLength = length();
1316     if (!matchLength)
1317         return std::min(index, ourLength);
1318
1319     // Optimization 1: fast case for strings of length 1.
1320     if (matchLength == 1) {
1321         if (is8Bit())
1322             return WTF::reverseFind(characters8(), ourLength, (*matchString)[0], index);
1323         return WTF::reverseFind(characters16(), ourLength, (*matchString)[0], index);
1324     }
1325
1326     // Check index & matchLength are in range.
1327     if (matchLength > ourLength)
1328         return notFound;
1329
1330     if (is8Bit()) {
1331         if (matchString->is8Bit())
1332             return reverseFindInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1333         return reverseFindInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1334     }
1335     
1336     if (matchString->is8Bit())
1337         return reverseFindInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1338
1339     return reverseFindInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1340 }
1341
1342 template <typename SearchCharacterType, typename MatchCharacterType>
1343 ALWAYS_INLINE static size_t reverseFindIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
1344 {
1345     // delta is the number of additional times to test; delta == 0 means test only once.
1346     unsigned delta = std::min(index, length - matchLength);
1347
1348     // keep looping until we match
1349     while (!equalIgnoringCase(searchCharacters + delta, matchCharacters, matchLength)) {
1350         if (!delta)
1351             return notFound;
1352         --delta;
1353     }
1354     return delta;
1355 }
1356
1357 size_t StringImpl::reverseFindIgnoringCase(StringImpl* matchString, unsigned index)
1358 {
1359     // Check for null or empty string to match against
1360     if (!matchString)
1361         return notFound;
1362     unsigned matchLength = matchString->length();
1363     unsigned ourLength = length();
1364     if (!matchLength)
1365         return std::min(index, ourLength);
1366
1367     // Check index & matchLength are in range.
1368     if (matchLength > ourLength)
1369         return notFound;
1370
1371     if (is8Bit()) {
1372         if (matchString->is8Bit())
1373             return reverseFindIgnoringCaseInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1374         return reverseFindIgnoringCaseInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1375     }
1376
1377     if (matchString->is8Bit())
1378         return reverseFindIgnoringCaseInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1379
1380     return reverseFindIgnoringCaseInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1381 }
1382
1383 ALWAYS_INLINE static bool equalInner(const StringImpl* stringImpl, unsigned startOffset, const char* matchString, unsigned matchLength, bool caseSensitive)
1384 {
1385     ASSERT(stringImpl);
1386     ASSERT(matchLength <= stringImpl->length());
1387     ASSERT(startOffset + matchLength <= stringImpl->length());
1388
1389     if (caseSensitive) {
1390         if (stringImpl->is8Bit())
1391             return equal(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1392         return equal(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1393     }
1394     if (stringImpl->is8Bit())
1395         return equalIgnoringCase(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1396     return equalIgnoringCase(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1397 }
1398
1399 ALWAYS_INLINE static bool equalInner(const StringImpl& stringImpl, unsigned startOffset, const StringImpl& matchString)
1400 {
1401     if (startOffset > stringImpl.length())
1402         return false;
1403     if (matchString.length() > stringImpl.length())
1404         return false;
1405     if (matchString.length() + startOffset > stringImpl.length())
1406         return false;
1407
1408     if (stringImpl.is8Bit()) {
1409         if (matchString.is8Bit())
1410             return equal(stringImpl.characters8() + startOffset, matchString.characters8(), matchString.length());
1411         return equal(stringImpl.characters8() + startOffset, matchString.characters16(), matchString.length());
1412     }
1413     if (matchString.is8Bit())
1414         return equal(stringImpl.characters16() + startOffset, matchString.characters8(), matchString.length());
1415     return equal(stringImpl.characters16() + startOffset, matchString.characters16(), matchString.length());
1416 }
1417
1418 bool StringImpl::startsWith(const StringImpl* str) const
1419 {
1420     if (!str)
1421         return false;
1422     return ::WTF::startsWith(*this, *str);
1423 }
1424
1425 bool StringImpl::startsWith(const StringImpl& str) const
1426 {
1427     return ::WTF::startsWith(*this, str);
1428 }
1429
1430 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl* prefix) const
1431 {
1432     if (!prefix)
1433         return false;
1434
1435     return ::WTF::startsWithIgnoringASCIICase(*this, *prefix);
1436 }
1437
1438 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl& prefix) const
1439 {
1440     return ::WTF::startsWithIgnoringASCIICase(*this, prefix);
1441 }
1442
1443 bool StringImpl::startsWith(UChar character) const
1444 {
1445     return m_length && (*this)[0] == character;
1446 }
1447
1448 bool StringImpl::startsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
1449 {
1450     ASSERT(matchLength);
1451     if (matchLength > length())
1452         return false;
1453     return equalInner(this, 0, matchString, matchLength, caseSensitive);
1454 }
1455
1456 bool StringImpl::hasInfixStartingAt(const StringImpl& matchString, unsigned startOffset) const
1457 {
1458     return equalInner(*this, startOffset, matchString);
1459 }
1460
1461 bool StringImpl::endsWith(StringImpl* suffix)
1462 {
1463     if (!suffix)
1464         return false;
1465
1466     return ::WTF::endsWith(*this, *suffix);
1467 }
1468
1469 bool StringImpl::endsWith(StringImpl& suffix)
1470 {
1471     return ::WTF::endsWith(*this, suffix);
1472 }
1473
1474 bool StringImpl::endsWith(StringImpl* matchString, bool caseSensitive)
1475 {
1476     ASSERT(matchString);
1477     if (m_length >= matchString->m_length) {
1478         unsigned start = m_length - matchString->m_length;
1479         return (caseSensitive ? find(matchString, start) : findIgnoringCase(matchString, start)) == start;
1480     }
1481     return false;
1482 }
1483
1484 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl* suffix) const
1485 {
1486     if (!suffix)
1487         return false;
1488
1489     return ::WTF::endsWithIgnoringASCIICase(*this, *suffix);
1490 }
1491
1492 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl& suffix) const
1493 {
1494     return ::WTF::endsWithIgnoringASCIICase(*this, suffix);
1495 }
1496
1497 bool StringImpl::endsWith(UChar character) const
1498 {
1499     return m_length && (*this)[m_length - 1] == character;
1500 }
1501
1502 bool StringImpl::endsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
1503 {
1504     ASSERT(matchLength);
1505     if (matchLength > length())
1506         return false;
1507     unsigned startOffset = length() - matchLength;
1508     return equalInner(this, startOffset, matchString, matchLength, caseSensitive);
1509 }
1510
1511 bool StringImpl::hasInfixEndingAt(const StringImpl& matchString, unsigned endOffset) const
1512 {
1513     if (endOffset < matchString.length())
1514         return false;
1515     return equalInner(*this, endOffset - matchString.length(), matchString);
1516 }
1517
1518 Ref<StringImpl> StringImpl::replace(UChar oldC, UChar newC)
1519 {
1520     if (oldC == newC)
1521         return *this;
1522     unsigned i;
1523     for (i = 0; i != m_length; ++i) {
1524         UChar c = is8Bit() ? m_data8[i] : m_data16[i];
1525         if (c == oldC)
1526             break;
1527     }
1528     if (i == m_length)
1529         return *this;
1530
1531     if (is8Bit()) {
1532         if (oldC > 0xff)
1533             // Looking for a 16 bit char in an 8 bit string, we're done.
1534             return *this;
1535
1536         if (newC <= 0xff) {
1537             LChar* data;
1538             LChar oldChar = static_cast<LChar>(oldC);
1539             LChar newChar = static_cast<LChar>(newC);
1540
1541             auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1542
1543             for (i = 0; i != m_length; ++i) {
1544                 LChar ch = m_data8[i];
1545                 if (ch == oldChar)
1546                     ch = newChar;
1547                 data[i] = ch;
1548             }
1549             return newImpl;
1550         }
1551
1552         // There is the possibility we need to up convert from 8 to 16 bit,
1553         // create a 16 bit string for the result.
1554         UChar* data;
1555         auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1556
1557         for (i = 0; i != m_length; ++i) {
1558             UChar ch = m_data8[i];
1559             if (ch == oldC)
1560                 ch = newC;
1561             data[i] = ch;
1562         }
1563
1564         return newImpl;
1565     }
1566
1567     UChar* data;
1568     auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1569
1570     for (i = 0; i != m_length; ++i) {
1571         UChar ch = m_data16[i];
1572         if (ch == oldC)
1573             ch = newC;
1574         data[i] = ch;
1575     }
1576     return newImpl;
1577 }
1578
1579 Ref<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str)
1580 {
1581     position = std::min(position, length());
1582     lengthToReplace = std::min(lengthToReplace, length() - position);
1583     unsigned lengthToInsert = str ? str->length() : 0;
1584     if (!lengthToReplace && !lengthToInsert)
1585         return *this;
1586
1587     if ((length() - lengthToReplace) >= (std::numeric_limits<unsigned>::max() - lengthToInsert))
1588         CRASH();
1589
1590     if (is8Bit() && (!str || str->is8Bit())) {
1591         LChar* data;
1592         auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1593         memcpy(data, m_data8, position * sizeof(LChar));
1594         if (str)
1595             memcpy(data + position, str->m_data8, lengthToInsert * sizeof(LChar));
1596         memcpy(data + position + lengthToInsert, m_data8 + position + lengthToReplace,
1597                (length() - position - lengthToReplace) * sizeof(LChar));
1598         return newImpl;
1599     }
1600     UChar* data;
1601     auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1602     if (is8Bit())
1603         for (unsigned i = 0; i < position; ++i)
1604             data[i] = m_data8[i];
1605     else
1606         memcpy(data, m_data16, position * sizeof(UChar));
1607     if (str) {
1608         if (str->is8Bit())
1609             for (unsigned i = 0; i < lengthToInsert; ++i)
1610                 data[i + position] = str->m_data8[i];
1611         else
1612             memcpy(data + position, str->m_data16, lengthToInsert * sizeof(UChar));
1613     }
1614     if (is8Bit()) {
1615         for (unsigned i = 0; i < length() - position - lengthToReplace; ++i)
1616             data[i + position + lengthToInsert] = m_data8[i + position + lengthToReplace];
1617     } else {
1618         memcpy(data + position + lengthToInsert, characters16() + position + lengthToReplace,
1619             (length() - position - lengthToReplace) * sizeof(UChar));
1620     }
1621     return newImpl;
1622 }
1623
1624 Ref<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
1625 {
1626     if (!replacement)
1627         return *this;
1628
1629     if (replacement->is8Bit())
1630         return replace(pattern, replacement->m_data8, replacement->length());
1631
1632     return replace(pattern, replacement->m_data16, replacement->length());
1633 }
1634
1635 Ref<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength)
1636 {
1637     ASSERT(replacement);
1638
1639     size_t srcSegmentStart = 0;
1640     unsigned matchCount = 0;
1641
1642     // Count the matches.
1643     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1644         ++matchCount;
1645         ++srcSegmentStart;
1646     }
1647
1648     // If we have 0 matches then we don't have to do any more work.
1649     if (!matchCount)
1650         return *this;
1651
1652     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1653         CRASH();
1654
1655     unsigned replaceSize = matchCount * repStrLength;
1656     unsigned newSize = m_length - matchCount;
1657     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1658         CRASH();
1659
1660     newSize += replaceSize;
1661
1662     // Construct the new data.
1663     size_t srcSegmentEnd;
1664     unsigned srcSegmentLength;
1665     srcSegmentStart = 0;
1666     unsigned dstOffset = 0;
1667
1668     if (is8Bit()) {
1669         LChar* data;
1670         auto newImpl = createUninitialized(newSize, data);
1671
1672         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1673             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1674             memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1675             dstOffset += srcSegmentLength;
1676             memcpy(data + dstOffset, replacement, repStrLength * sizeof(LChar));
1677             dstOffset += repStrLength;
1678             srcSegmentStart = srcSegmentEnd + 1;
1679         }
1680
1681         srcSegmentLength = m_length - srcSegmentStart;
1682         memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1683
1684         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1685
1686         return newImpl;
1687     }
1688
1689     UChar* data;
1690     auto newImpl = createUninitialized(newSize, data);
1691
1692     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1693         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1694         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1695
1696         dstOffset += srcSegmentLength;
1697         for (unsigned i = 0; i < repStrLength; ++i)
1698             data[i + dstOffset] = replacement[i];
1699
1700         dstOffset += repStrLength;
1701         srcSegmentStart = srcSegmentEnd + 1;
1702     }
1703
1704     srcSegmentLength = m_length - srcSegmentStart;
1705     memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1706
1707     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1708
1709     return newImpl;
1710 }
1711
1712 Ref<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength)
1713 {
1714     ASSERT(replacement);
1715
1716     size_t srcSegmentStart = 0;
1717     unsigned matchCount = 0;
1718
1719     // Count the matches.
1720     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1721         ++matchCount;
1722         ++srcSegmentStart;
1723     }
1724
1725     // If we have 0 matches then we don't have to do any more work.
1726     if (!matchCount)
1727         return *this;
1728
1729     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1730         CRASH();
1731
1732     unsigned replaceSize = matchCount * repStrLength;
1733     unsigned newSize = m_length - matchCount;
1734     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1735         CRASH();
1736
1737     newSize += replaceSize;
1738
1739     // Construct the new data.
1740     size_t srcSegmentEnd;
1741     unsigned srcSegmentLength;
1742     srcSegmentStart = 0;
1743     unsigned dstOffset = 0;
1744
1745     if (is8Bit()) {
1746         UChar* data;
1747         auto newImpl = createUninitialized(newSize, data);
1748
1749         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1750             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1751             for (unsigned i = 0; i < srcSegmentLength; ++i)
1752                 data[i + dstOffset] = m_data8[i + srcSegmentStart];
1753
1754             dstOffset += srcSegmentLength;
1755             memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));
1756
1757             dstOffset += repStrLength;
1758             srcSegmentStart = srcSegmentEnd + 1;
1759         }
1760
1761         srcSegmentLength = m_length - srcSegmentStart;
1762         for (unsigned i = 0; i < srcSegmentLength; ++i)
1763             data[i + dstOffset] = m_data8[i + srcSegmentStart];
1764
1765         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1766
1767         return newImpl;
1768     }
1769
1770     UChar* data;
1771     auto newImpl = createUninitialized(newSize, data);
1772
1773     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1774         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1775         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1776
1777         dstOffset += srcSegmentLength;
1778         memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));
1779
1780         dstOffset += repStrLength;
1781         srcSegmentStart = srcSegmentEnd + 1;
1782     }
1783
1784     srcSegmentLength = m_length - srcSegmentStart;
1785     memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1786
1787     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1788
1789     return newImpl;
1790 }
1791
1792 Ref<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
1793 {
1794     if (!pattern || !replacement)
1795         return *this;
1796
1797     unsigned patternLength = pattern->length();
1798     if (!patternLength)
1799         return *this;
1800         
1801     unsigned repStrLength = replacement->length();
1802     size_t srcSegmentStart = 0;
1803     unsigned matchCount = 0;
1804     
1805     // Count the matches.
1806     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1807         ++matchCount;
1808         srcSegmentStart += patternLength;
1809     }
1810     
1811     // If we have 0 matches, we don't have to do any more work
1812     if (!matchCount)
1813         return *this;
1814     
1815     unsigned newSize = m_length - matchCount * patternLength;
1816     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1817         CRASH();
1818
1819     if (newSize > (std::numeric_limits<unsigned>::max() - matchCount * repStrLength))
1820         CRASH();
1821
1822     newSize += matchCount * repStrLength;
1823
1824     
1825     // Construct the new data
1826     size_t srcSegmentEnd;
1827     unsigned srcSegmentLength;
1828     srcSegmentStart = 0;
1829     unsigned dstOffset = 0;
1830     bool srcIs8Bit = is8Bit();
1831     bool replacementIs8Bit = replacement->is8Bit();
1832     
1833     // There are 4 cases:
1834     // 1. This and replacement are both 8 bit.
1835     // 2. This and replacement are both 16 bit.
1836     // 3. This is 8 bit and replacement is 16 bit.
1837     // 4. This is 16 bit and replacement is 8 bit.
1838     if (srcIs8Bit && replacementIs8Bit) {
1839         // Case 1
1840         LChar* data;
1841         auto newImpl = createUninitialized(newSize, data);
1842         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1843             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1844             memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1845             dstOffset += srcSegmentLength;
1846             memcpy(data + dstOffset, replacement->m_data8, repStrLength * sizeof(LChar));
1847             dstOffset += repStrLength;
1848             srcSegmentStart = srcSegmentEnd + patternLength;
1849         }
1850
1851         srcSegmentLength = m_length - srcSegmentStart;
1852         memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1853
1854         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1855
1856         return newImpl;
1857     }
1858
1859     UChar* data;
1860     auto newImpl = createUninitialized(newSize, data);
1861     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1862         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1863         if (srcIs8Bit) {
1864             // Case 3.
1865             for (unsigned i = 0; i < srcSegmentLength; ++i)
1866                 data[i + dstOffset] = m_data8[i + srcSegmentStart];
1867         } else {
1868             // Case 2 & 4.
1869             memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1870         }
1871         dstOffset += srcSegmentLength;
1872         if (replacementIs8Bit) {
1873             // Cases 2 & 3.
1874             for (unsigned i = 0; i < repStrLength; ++i)
1875                 data[i + dstOffset] = replacement->m_data8[i];
1876         } else {
1877             // Case 4
1878             memcpy(data + dstOffset, replacement->m_data16, repStrLength * sizeof(UChar));
1879         }
1880         dstOffset += repStrLength;
1881         srcSegmentStart = srcSegmentEnd + patternLength;
1882     }
1883
1884     srcSegmentLength = m_length - srcSegmentStart;
1885     if (srcIs8Bit) {
1886         // Case 3.
1887         for (unsigned i = 0; i < srcSegmentLength; ++i)
1888             data[i + dstOffset] = m_data8[i + srcSegmentStart];
1889     } else {
1890         // Cases 2 & 4.
1891         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1892     }
1893
1894     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1895
1896     return newImpl;
1897 }
1898
1899 bool equal(const StringImpl* a, const StringImpl* b)
1900 {
1901     return equalCommon(a, b);
1902 }
1903
1904 template <typename CharType>
1905 inline bool equalInternal(const StringImpl* a, const CharType* b, unsigned length)
1906 {
1907     if (!a)
1908         return !b;
1909     if (!b)
1910         return false;
1911
1912     if (a->length() != length)
1913         return false;
1914     if (a->is8Bit())
1915         return equal(a->characters8(), b, length);
1916     return equal(a->characters16(), b, length);
1917 }
1918
1919 bool equal(const StringImpl* a, const LChar* b, unsigned length)
1920 {
1921     return equalInternal(a, b, length);
1922 }
1923
1924 bool equal(const StringImpl* a, const UChar* b, unsigned length)
1925 {
1926     return equalInternal(a, b, length);
1927 }
1928
1929 bool equal(const StringImpl* a, const LChar* b)
1930 {
1931     if (!a)
1932         return !b;
1933     if (!b)
1934         return !a;
1935
1936     unsigned length = a->length();
1937
1938     if (a->is8Bit()) {
1939         const LChar* aPtr = a->characters8();
1940         for (unsigned i = 0; i != length; ++i) {
1941             LChar bc = b[i];
1942             LChar ac = aPtr[i];
1943             if (!bc)
1944                 return false;
1945             if (ac != bc)
1946                 return false;
1947         }
1948
1949         return !b[length];
1950     }
1951
1952     const UChar* aPtr = a->characters16();
1953     for (unsigned i = 0; i != length; ++i) {
1954         LChar bc = b[i];
1955         if (!bc)
1956             return false;
1957         if (aPtr[i] != bc)
1958             return false;
1959     }
1960
1961     return !b[length];
1962 }
1963
1964 bool equal(const StringImpl& a, const StringImpl& b)
1965 {
1966     return equalCommon(a, b);
1967 }
1968
1969 bool equalIgnoringCase(const StringImpl* a, const StringImpl* b)
1970 {
1971     if (a == b)
1972         return true;
1973     if (!a || !b)
1974         return false;
1975
1976     return CaseFoldingHash::equal(a, b);
1977 }
1978
1979 bool equalIgnoringCase(const StringImpl* a, const LChar* b)
1980 {
1981     if (!a)
1982         return !b;
1983     if (!b)
1984         return !a;
1985
1986     unsigned length = a->length();
1987
1988     // Do a faster loop for the case where all the characters are ASCII.
1989     UChar ored = 0;
1990     bool equal = true;
1991     if (a->is8Bit()) {
1992         const LChar* as = a->characters8();
1993         for (unsigned i = 0; i != length; ++i) {
1994             LChar bc = b[i];
1995             if (!bc)
1996                 return false;
1997             UChar ac = as[i];
1998             ored |= ac;
1999             equal = equal && (toASCIILower(ac) == toASCIILower(bc));
2000         }
2001         
2002         // Do a slower implementation for cases that include non-ASCII characters.
2003         if (ored & ~0x7F) {
2004             equal = true;
2005             for (unsigned i = 0; i != length; ++i)
2006                 equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
2007         }
2008         
2009         return equal && !b[length];        
2010     }
2011
2012     const UChar* as = a->characters16();
2013     for (unsigned i = 0; i != length; ++i) {
2014         LChar bc = b[i];
2015         if (!bc)
2016             return false;
2017         UChar ac = as[i];
2018         ored |= ac;
2019         equal = equal && (toASCIILower(ac) == toASCIILower(bc));
2020     }
2021
2022     // Do a slower implementation for cases that include non-ASCII characters.
2023     if (ored & ~0x7F) {
2024         equal = true;
2025         for (unsigned i = 0; i != length; ++i) {
2026             equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
2027         }
2028     }
2029
2030     return equal && !b[length];
2031 }
2032
2033 bool equalIgnoringCaseNonNull(const StringImpl* a, const StringImpl* b)
2034 {
2035     ASSERT(a && b);
2036     if (a == b)
2037         return true;
2038
2039     unsigned length = a->length();
2040     if (length != b->length())
2041         return false;
2042
2043     if (a->is8Bit()) {
2044         if (b->is8Bit())
2045             return equalIgnoringCase(a->characters8(), b->characters8(), length);
2046
2047         return equalIgnoringCase(b->characters16(), a->characters8(), length);
2048     }
2049
2050     if (b->is8Bit())
2051         return equalIgnoringCase(a->characters16(), b->characters8(), length);
2052
2053     return equalIgnoringCase(a->characters16(), b->characters16(), length);
2054 }
2055
2056 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
2057 {
2058     if (!a && b && !b->length())
2059         return true;
2060     if (!b && a && !a->length())
2061         return true;
2062     return equal(a, b);
2063 }
2064
2065 bool equalIgnoringASCIICase(const StringImpl& a, const StringImpl& b)
2066 {
2067     return equalIgnoringASCIICaseCommon(a, b);
2068 }
2069
2070 bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl*b)
2071 {
2072     if (a == b)
2073         return true;
2074     if (!a || !b)
2075         return false;
2076     return equalIgnoringASCIICaseCommon(*a, *b);
2077 }
2078
2079 bool equalIgnoringASCIICase(const StringImpl& a, const char* b, unsigned bLength)
2080 {
2081     if (bLength != a.length())
2082         return false;
2083
2084     if (a.is8Bit())
2085         return equalIgnoringASCIICase(a.characters8(), b, bLength);
2086
2087     return equalIgnoringASCIICase(a.characters16(), b, bLength);
2088 }
2089
2090 bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b)
2091 {
2092     ASSERT(a);
2093     ASSERT(b);
2094     return equalIgnoringASCIICaseCommon(*a, *b);
2095 }
2096
2097 UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality)
2098 {
2099     for (unsigned i = 0; i < m_length; ++i) {
2100         UCharDirection charDirection = u_charDirection(is8Bit() ? m_data8[i] : m_data16[i]);
2101         if (charDirection == U_LEFT_TO_RIGHT) {
2102             if (hasStrongDirectionality)
2103                 *hasStrongDirectionality = true;
2104             return U_LEFT_TO_RIGHT;
2105         }
2106         if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
2107             if (hasStrongDirectionality)
2108                 *hasStrongDirectionality = true;
2109             return U_RIGHT_TO_LEFT;
2110         }
2111     }
2112     if (hasStrongDirectionality)
2113         *hasStrongDirectionality = false;
2114     return U_LEFT_TO_RIGHT;
2115 }
2116
2117 Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>& buffer)
2118 {
2119     unsigned length = buffer.length();
2120     if (!length)
2121         return *empty();
2122     return adoptRef(*new StringImpl(buffer.release(), length));
2123 }
2124
2125 Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>& buffer)
2126 {
2127     unsigned length = buffer.length();
2128     if (!length)
2129         return *empty();
2130     return adoptRef(*new StringImpl(buffer.release(), length));
2131 }
2132
2133 size_t StringImpl::sizeInBytes() const
2134 {
2135     // FIXME: support substrings
2136     size_t size = length();
2137     if (!is8Bit())
2138         size *= 2;
2139     return size + sizeof(*this);
2140 }
2141
2142 // Helper to write a three-byte UTF-8 code point to the buffer, caller must check room is available.
2143 static inline void putUTF8Triple(char*& buffer, UChar ch)
2144 {
2145     ASSERT(ch >= 0x0800);
2146     *buffer++ = static_cast<char>(((ch >> 12) & 0x0F) | 0xE0);
2147     *buffer++ = static_cast<char>(((ch >> 6) & 0x3F) | 0x80);
2148     *buffer++ = static_cast<char>((ch & 0x3F) | 0x80);
2149 }
2150
2151 bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode)
2152 {
2153     if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) {
2154         const UChar* charactersEnd = characters + length;
2155         char* bufferEnd = buffer + bufferSize;
2156         while (characters < charactersEnd) {
2157             // Use strict conversion to detect unpaired surrogates.
2158             ConversionResult result = convertUTF16ToUTF8(&characters, charactersEnd, &buffer, bufferEnd, true);
2159             ASSERT(result != targetExhausted);
2160             // Conversion fails when there is an unpaired surrogate.
2161             // Put replacement character (U+FFFD) instead of the unpaired surrogate.
2162             if (result != conversionOK) {
2163                 ASSERT((0xD800 <= *characters && *characters <= 0xDFFF));
2164                 // There should be room left, since one UChar hasn't been converted.
2165                 ASSERT((buffer + 3) <= bufferEnd);
2166                 putUTF8Triple(buffer, replacementCharacter);
2167                 ++characters;
2168             }
2169         }
2170     } else {
2171         bool strict = mode == StrictConversion;
2172         const UChar* originalCharacters = characters;
2173         ConversionResult result = convertUTF16ToUTF8(&characters, characters + length, &buffer, buffer + bufferSize, strict);
2174         ASSERT(result != targetExhausted); // (length * 3) should be sufficient for any conversion
2175
2176         // Only produced from strict conversion.
2177         if (result == sourceIllegal) {
2178             ASSERT(strict);
2179             return false;
2180         }
2181
2182         // Check for an unconverted high surrogate.
2183         if (result == sourceExhausted) {
2184             if (strict)
2185                 return false;
2186             // This should be one unpaired high surrogate. Treat it the same
2187             // was as an unpaired high surrogate would have been handled in
2188             // the middle of a string with non-strict conversion - which is
2189             // to say, simply encode it to UTF-8.
2190             ASSERT_UNUSED(
2191                 originalCharacters, (characters + 1) == (originalCharacters + length));
2192             ASSERT((*characters >= 0xD800) && (*characters <= 0xDBFF));
2193             // There should be room left, since one UChar hasn't been converted.
2194             ASSERT((buffer + 3) <= (buffer + bufferSize));
2195             putUTF8Triple(buffer, *characters);
2196         }
2197     }
2198     
2199     return true;
2200 }
2201
2202 CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length)
2203 {
2204     if (!length)
2205         return CString("", 0);
2206     if (length > std::numeric_limits<unsigned>::max() / 3)
2207         return CString();
2208     Vector<char, 1024> bufferVector(length * 3);
2209     char* buffer = bufferVector.data();
2210     const LChar* source = characters;
2211     ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size());
2212     ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2213     return CString(bufferVector.data(), buffer - bufferVector.data());
2214 }
2215
2216 CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode)
2217 {
2218     if (!length)
2219         return CString("", 0);
2220     if (length > std::numeric_limits<unsigned>::max() / 3)
2221         return CString();
2222     Vector<char, 1024> bufferVector(length * 3);
2223     char* buffer = bufferVector.data();
2224     if (!utf8Impl(characters, length, buffer, bufferVector.size(), mode))
2225         return CString();
2226     return CString(bufferVector.data(), buffer - bufferVector.data());
2227 }
2228
2229 CString StringImpl::utf8ForRange(unsigned offset, unsigned length, ConversionMode mode) const
2230 {
2231     ASSERT(offset <= this->length());
2232     ASSERT(offset + length <= this->length());
2233     
2234     if (!length)
2235         return CString("", 0);
2236
2237     // Allocate a buffer big enough to hold all the characters
2238     // (an individual UTF-16 UChar can only expand to 3 UTF-8 bytes).
2239     // Optimization ideas, if we find this function is hot:
2240     //  * We could speculatively create a CStringBuffer to contain 'length' 
2241     //    characters, and resize if necessary (i.e. if the buffer contains
2242     //    non-ascii characters). (Alternatively, scan the buffer first for
2243     //    ascii characters, so we know this will be sufficient).
2244     //  * We could allocate a CStringBuffer with an appropriate size to
2245     //    have a good chance of being able to write the string into the
2246     //    buffer without reallocing (say, 1.5 x length).
2247     if (length > std::numeric_limits<unsigned>::max() / 3)
2248         return CString();
2249     Vector<char, 1024> bufferVector(length * 3);
2250
2251     char* buffer = bufferVector.data();
2252
2253     if (is8Bit()) {
2254         const LChar* characters = this->characters8() + offset;
2255
2256         ConversionResult result = convertLatin1ToUTF8(&characters, characters + length, &buffer, buffer + bufferVector.size());
2257         ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2258     } else {
2259         if (!utf8Impl(this->characters16() + offset, length, buffer, bufferVector.size(), mode))
2260             return CString();
2261     }
2262
2263     return CString(bufferVector.data(), buffer - bufferVector.data());
2264 }
2265
2266 CString StringImpl::utf8(ConversionMode mode) const
2267 {
2268     return utf8ForRange(0, length(), mode);
2269 }
2270
2271 // Table is based on ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
2272 const UChar StringImpl::latin1CaseFoldTable[256] = {
2273     0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
2274     0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, 
2275     0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, 
2276     0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f,
2277     0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2278     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f,
2279     0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2280     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f,
2281     0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f,
2282     0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f,
2283     0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, 0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af,
2284     0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x03bc, 0x00b6, 0x00b7, 0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf,
2285     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2286     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00d7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00df,
2287     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2288     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff, 
2289 };
2290
2291 bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b)
2292 {
2293     if (!b)
2294         return !aLength;
2295     if (aLength != b->length())
2296         return false;
2297     if (b->is8Bit()) {
2298         const LChar* bCharacters = b->characters8();
2299         for (unsigned i = 0; i < aLength; ++i) {
2300             if (a[i] != bCharacters[i])
2301                 return false;
2302         }
2303         return true;
2304     }
2305     return !memcmp(a, b->characters16(), b->length() * sizeof(UChar));
2306 }
2307
2308 } // namespace WTF