HTMLElement::nodeName should not upper case non-ASCII characters
[WebKit.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 template<StringImpl::CaseConvertType type, typename CharacterType>
683 ALWAYS_INLINE Ref<StringImpl> StringImpl::convertASCIICase(StringImpl& impl, const CharacterType* data, unsigned length)
684 {
685     unsigned failingIndex;
686     for (unsigned i = 0; i < length; ++i) {
687         CharacterType character = data[i];
688         if (type == CaseConvertType::Lower ? UNLIKELY(isASCIIUpper(character)) : LIKELY(isASCIILower(character))) {
689             failingIndex = i;
690             goto SlowPath;
691         }
692     }
693     return impl;
694
695 SlowPath:
696     CharacterType* newData;
697     Ref<StringImpl> newImpl = createUninitializedInternalNonEmpty(length, newData);
698     for (unsigned i = 0; i < failingIndex; ++i)
699         newData[i] = data[i];
700     for (unsigned i = failingIndex; i < length; ++i)
701         newData[i] = type == CaseConvertType::Lower ? toASCIILower(data[i]) : toASCIIUpper(data[i]);
702     return newImpl;
703 }
704
705 Ref<StringImpl> StringImpl::convertToASCIILowercase()
706 {
707     if (is8Bit())
708         return convertASCIICase<CaseConvertType::Lower>(*this, m_data8, m_length);
709     return convertASCIICase<CaseConvertType::Lower>(*this, m_data16, m_length);
710 }
711
712 Ref<StringImpl> StringImpl::convertToASCIIUppercase()
713 {
714     if (is8Bit())
715         return convertASCIICase<CaseConvertType::Upper>(*this, m_data8, m_length);
716     return convertASCIICase<CaseConvertType::Upper>(*this, m_data16, m_length);
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 size_t StringImpl::find(StringImpl* matchString)
1095 {
1096     // Check for null string to match against
1097     if (UNLIKELY(!matchString))
1098         return notFound;
1099     unsigned matchLength = matchString->length();
1100
1101     // Optimization 1: fast case for strings of length 1.
1102     if (matchLength == 1) {
1103         if (is8Bit()) {
1104             if (matchString->is8Bit())
1105                 return WTF::find(characters8(), length(), matchString->characters8()[0]);
1106             return WTF::find(characters8(), length(), matchString->characters16()[0]);
1107         }
1108         if (matchString->is8Bit())
1109             return WTF::find(characters16(), length(), matchString->characters8()[0]);
1110         return WTF::find(characters16(), length(), matchString->characters16()[0]);
1111     }
1112
1113     // Check matchLength is in range.
1114     if (matchLength > length())
1115         return notFound;
1116
1117     // Check for empty string to match against
1118     if (UNLIKELY(!matchLength))
1119         return 0;
1120
1121     if (is8Bit()) {
1122         if (matchString->is8Bit())
1123             return findInner(characters8(), matchString->characters8(), 0, length(), matchLength);
1124         return findInner(characters8(), matchString->characters16(), 0, length(), matchLength);
1125     }
1126
1127     if (matchString->is8Bit())
1128         return findInner(characters16(), matchString->characters8(), 0, length(), matchLength);
1129
1130     return findInner(characters16(), matchString->characters16(), 0, length(), matchLength);
1131 }
1132
1133 size_t StringImpl::find(StringImpl* matchString, unsigned index)
1134 {
1135     // Check for null or empty string to match against
1136     if (UNLIKELY(!matchString))
1137         return notFound;
1138
1139     return findCommon(*this, *matchString, index);
1140 }
1141
1142 template <typename SearchCharacterType, typename MatchCharacterType>
1143 ALWAYS_INLINE static size_t findIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
1144 {
1145     // delta is the number of additional times to test; delta == 0 means test only once.
1146     unsigned delta = searchLength - matchLength;
1147
1148     unsigned i = 0;
1149     // keep looping until we match
1150     while (!equalIgnoringCase(searchCharacters + i, matchCharacters, matchLength)) {
1151         if (i == delta)
1152             return notFound;
1153         ++i;
1154     }
1155     return index + i;
1156 }
1157
1158 size_t StringImpl::findIgnoringCase(StringImpl* matchString, unsigned index)
1159 {
1160     // Check for null or empty string to match against
1161     if (!matchString)
1162         return notFound;
1163     unsigned matchLength = matchString->length();
1164     if (!matchLength)
1165         return std::min(index, length());
1166
1167     // Check index & matchLength are in range.
1168     if (index > length())
1169         return notFound;
1170     unsigned searchLength = length() - index;
1171     if (matchLength > searchLength)
1172         return notFound;
1173
1174     if (is8Bit()) {
1175         if (matchString->is8Bit())
1176             return findIgnoringCaseInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
1177         return findIgnoringCaseInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
1178     }
1179
1180     if (matchString->is8Bit())
1181         return findIgnoringCaseInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength);
1182
1183     return findIgnoringCaseInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
1184 }
1185
1186 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString) const
1187 {
1188     return ::WTF::findIgnoringASCIICase(*this, matchString, 0);
1189 }
1190
1191 size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString, unsigned startOffset) const
1192 {
1193     return ::WTF::findIgnoringASCIICase(*this, matchString, startOffset);
1194 }
1195
1196 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString) const
1197 {
1198     if (!matchString)
1199         return notFound;
1200     return ::WTF::findIgnoringASCIICase(*this, *matchString, 0);
1201 }
1202
1203 size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString, unsigned startOffset) const
1204 {
1205     if (!matchString)
1206         return notFound;
1207     return ::WTF::findIgnoringASCIICase(*this, *matchString, startOffset);
1208 }
1209
1210 size_t StringImpl::findNextLineStart(unsigned index)
1211 {
1212     if (is8Bit())
1213         return WTF::findNextLineStart(characters8(), m_length, index);
1214     return WTF::findNextLineStart(characters16(), m_length, index);
1215 }
1216
1217 size_t StringImpl::reverseFind(UChar c, unsigned index)
1218 {
1219     if (is8Bit())
1220         return WTF::reverseFind(characters8(), m_length, c, index);
1221     return WTF::reverseFind(characters16(), m_length, c, index);
1222 }
1223
1224 template <typename SearchCharacterType, typename MatchCharacterType>
1225 ALWAYS_INLINE static size_t reverseFindInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
1226 {
1227     // Optimization: keep a running hash of the strings,
1228     // only call equal if the hashes match.
1229
1230     // delta is the number of additional times to test; delta == 0 means test only once.
1231     unsigned delta = std::min(index, length - matchLength);
1232     
1233     unsigned searchHash = 0;
1234     unsigned matchHash = 0;
1235     for (unsigned i = 0; i < matchLength; ++i) {
1236         searchHash += searchCharacters[delta + i];
1237         matchHash += matchCharacters[i];
1238     }
1239
1240     // keep looping until we match
1241     while (searchHash != matchHash || !equal(searchCharacters + delta, matchCharacters, matchLength)) {
1242         if (!delta)
1243             return notFound;
1244         --delta;
1245         searchHash -= searchCharacters[delta + matchLength];
1246         searchHash += searchCharacters[delta];
1247     }
1248     return delta;
1249 }
1250
1251 size_t StringImpl::reverseFind(StringImpl* matchString, unsigned index)
1252 {
1253     // Check for null or empty string to match against
1254     if (!matchString)
1255         return notFound;
1256     unsigned matchLength = matchString->length();
1257     unsigned ourLength = length();
1258     if (!matchLength)
1259         return std::min(index, ourLength);
1260
1261     // Optimization 1: fast case for strings of length 1.
1262     if (matchLength == 1) {
1263         if (is8Bit())
1264             return WTF::reverseFind(characters8(), ourLength, (*matchString)[0], index);
1265         return WTF::reverseFind(characters16(), ourLength, (*matchString)[0], index);
1266     }
1267
1268     // Check index & matchLength are in range.
1269     if (matchLength > ourLength)
1270         return notFound;
1271
1272     if (is8Bit()) {
1273         if (matchString->is8Bit())
1274             return reverseFindInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1275         return reverseFindInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1276     }
1277     
1278     if (matchString->is8Bit())
1279         return reverseFindInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1280
1281     return reverseFindInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1282 }
1283
1284 template <typename SearchCharacterType, typename MatchCharacterType>
1285 ALWAYS_INLINE static size_t reverseFindIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
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     // keep looping until we match
1291     while (!equalIgnoringCase(searchCharacters + delta, matchCharacters, matchLength)) {
1292         if (!delta)
1293             return notFound;
1294         --delta;
1295     }
1296     return delta;
1297 }
1298
1299 size_t StringImpl::reverseFindIgnoringCase(StringImpl* matchString, unsigned index)
1300 {
1301     // Check for null or empty string to match against
1302     if (!matchString)
1303         return notFound;
1304     unsigned matchLength = matchString->length();
1305     unsigned ourLength = length();
1306     if (!matchLength)
1307         return std::min(index, ourLength);
1308
1309     // Check index & matchLength are in range.
1310     if (matchLength > ourLength)
1311         return notFound;
1312
1313     if (is8Bit()) {
1314         if (matchString->is8Bit())
1315             return reverseFindIgnoringCaseInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
1316         return reverseFindIgnoringCaseInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
1317     }
1318
1319     if (matchString->is8Bit())
1320         return reverseFindIgnoringCaseInner(characters16(), matchString->characters8(), index, ourLength, matchLength);
1321
1322     return reverseFindIgnoringCaseInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
1323 }
1324
1325 ALWAYS_INLINE static bool equalInner(const StringImpl* stringImpl, unsigned startOffset, const char* matchString, unsigned matchLength, bool caseSensitive)
1326 {
1327     ASSERT(stringImpl);
1328     ASSERT(matchLength <= stringImpl->length());
1329     ASSERT(startOffset + matchLength <= stringImpl->length());
1330
1331     if (caseSensitive) {
1332         if (stringImpl->is8Bit())
1333             return equal(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1334         return equal(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1335     }
1336     if (stringImpl->is8Bit())
1337         return equalIgnoringCase(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1338     return equalIgnoringCase(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
1339 }
1340
1341 ALWAYS_INLINE static bool equalInner(const StringImpl& stringImpl, unsigned startOffset, const StringImpl& matchString)
1342 {
1343     if (startOffset > stringImpl.length())
1344         return false;
1345     if (matchString.length() > stringImpl.length())
1346         return false;
1347     if (matchString.length() + startOffset > stringImpl.length())
1348         return false;
1349
1350     if (stringImpl.is8Bit()) {
1351         if (matchString.is8Bit())
1352             return equal(stringImpl.characters8() + startOffset, matchString.characters8(), matchString.length());
1353         return equal(stringImpl.characters8() + startOffset, matchString.characters16(), matchString.length());
1354     }
1355     if (matchString.is8Bit())
1356         return equal(stringImpl.characters16() + startOffset, matchString.characters8(), matchString.length());
1357     return equal(stringImpl.characters16() + startOffset, matchString.characters16(), matchString.length());
1358 }
1359
1360 bool StringImpl::startsWith(const StringImpl* str) const
1361 {
1362     if (!str)
1363         return false;
1364     return ::WTF::startsWith(*this, *str);
1365 }
1366
1367 bool StringImpl::startsWith(const StringImpl& str) const
1368 {
1369     return ::WTF::startsWith(*this, str);
1370 }
1371
1372 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl* prefix) const
1373 {
1374     if (!prefix)
1375         return false;
1376
1377     return ::WTF::startsWithIgnoringASCIICase(*this, *prefix);
1378 }
1379
1380 bool StringImpl::startsWithIgnoringASCIICase(const StringImpl& prefix) const
1381 {
1382     return ::WTF::startsWithIgnoringASCIICase(*this, prefix);
1383 }
1384
1385 bool StringImpl::startsWith(UChar character) const
1386 {
1387     return m_length && (*this)[0] == character;
1388 }
1389
1390 bool StringImpl::startsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
1391 {
1392     ASSERT(matchLength);
1393     if (matchLength > length())
1394         return false;
1395     return equalInner(this, 0, matchString, matchLength, caseSensitive);
1396 }
1397
1398 bool StringImpl::hasInfixStartingAt(const StringImpl& matchString, unsigned startOffset) const
1399 {
1400     return equalInner(*this, startOffset, matchString);
1401 }
1402
1403 bool StringImpl::endsWith(StringImpl* suffix)
1404 {
1405     if (!suffix)
1406         return false;
1407
1408     return ::WTF::endsWith(*this, *suffix);
1409 }
1410
1411 bool StringImpl::endsWith(StringImpl& suffix)
1412 {
1413     return ::WTF::endsWith(*this, suffix);
1414 }
1415
1416 bool StringImpl::endsWith(StringImpl* matchString, bool caseSensitive)
1417 {
1418     ASSERT(matchString);
1419     if (m_length >= matchString->m_length) {
1420         unsigned start = m_length - matchString->m_length;
1421         return (caseSensitive ? find(matchString, start) : findIgnoringCase(matchString, start)) == start;
1422     }
1423     return false;
1424 }
1425
1426 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl* suffix) const
1427 {
1428     if (!suffix)
1429         return false;
1430
1431     return ::WTF::endsWithIgnoringASCIICase(*this, *suffix);
1432 }
1433
1434 bool StringImpl::endsWithIgnoringASCIICase(const StringImpl& suffix) const
1435 {
1436     return ::WTF::endsWithIgnoringASCIICase(*this, suffix);
1437 }
1438
1439 bool StringImpl::endsWith(UChar character) const
1440 {
1441     return m_length && (*this)[m_length - 1] == character;
1442 }
1443
1444 bool StringImpl::endsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
1445 {
1446     ASSERT(matchLength);
1447     if (matchLength > length())
1448         return false;
1449     unsigned startOffset = length() - matchLength;
1450     return equalInner(this, startOffset, matchString, matchLength, caseSensitive);
1451 }
1452
1453 bool StringImpl::hasInfixEndingAt(const StringImpl& matchString, unsigned endOffset) const
1454 {
1455     if (endOffset < matchString.length())
1456         return false;
1457     return equalInner(*this, endOffset - matchString.length(), matchString);
1458 }
1459
1460 Ref<StringImpl> StringImpl::replace(UChar oldC, UChar newC)
1461 {
1462     if (oldC == newC)
1463         return *this;
1464     unsigned i;
1465     for (i = 0; i != m_length; ++i) {
1466         UChar c = is8Bit() ? m_data8[i] : m_data16[i];
1467         if (c == oldC)
1468             break;
1469     }
1470     if (i == m_length)
1471         return *this;
1472
1473     if (is8Bit()) {
1474         if (oldC > 0xff)
1475             // Looking for a 16 bit char in an 8 bit string, we're done.
1476             return *this;
1477
1478         if (newC <= 0xff) {
1479             LChar* data;
1480             LChar oldChar = static_cast<LChar>(oldC);
1481             LChar newChar = static_cast<LChar>(newC);
1482
1483             auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1484
1485             for (i = 0; i != m_length; ++i) {
1486                 LChar ch = m_data8[i];
1487                 if (ch == oldChar)
1488                     ch = newChar;
1489                 data[i] = ch;
1490             }
1491             return newImpl;
1492         }
1493
1494         // There is the possibility we need to up convert from 8 to 16 bit,
1495         // create a 16 bit string for the result.
1496         UChar* data;
1497         auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1498
1499         for (i = 0; i != m_length; ++i) {
1500             UChar ch = m_data8[i];
1501             if (ch == oldC)
1502                 ch = newC;
1503             data[i] = ch;
1504         }
1505
1506         return newImpl;
1507     }
1508
1509     UChar* data;
1510     auto newImpl = createUninitializedInternalNonEmpty(m_length, data);
1511
1512     for (i = 0; i != m_length; ++i) {
1513         UChar ch = m_data16[i];
1514         if (ch == oldC)
1515             ch = newC;
1516         data[i] = ch;
1517     }
1518     return newImpl;
1519 }
1520
1521 Ref<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str)
1522 {
1523     position = std::min(position, length());
1524     lengthToReplace = std::min(lengthToReplace, length() - position);
1525     unsigned lengthToInsert = str ? str->length() : 0;
1526     if (!lengthToReplace && !lengthToInsert)
1527         return *this;
1528
1529     if ((length() - lengthToReplace) >= (std::numeric_limits<unsigned>::max() - lengthToInsert))
1530         CRASH();
1531
1532     if (is8Bit() && (!str || str->is8Bit())) {
1533         LChar* data;
1534         auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1535         memcpy(data, m_data8, position * sizeof(LChar));
1536         if (str)
1537             memcpy(data + position, str->m_data8, lengthToInsert * sizeof(LChar));
1538         memcpy(data + position + lengthToInsert, m_data8 + position + lengthToReplace,
1539                (length() - position - lengthToReplace) * sizeof(LChar));
1540         return newImpl;
1541     }
1542     UChar* data;
1543     auto newImpl = createUninitialized(length() - lengthToReplace + lengthToInsert, data);
1544     if (is8Bit())
1545         for (unsigned i = 0; i < position; ++i)
1546             data[i] = m_data8[i];
1547     else
1548         memcpy(data, m_data16, position * sizeof(UChar));
1549     if (str) {
1550         if (str->is8Bit())
1551             for (unsigned i = 0; i < lengthToInsert; ++i)
1552                 data[i + position] = str->m_data8[i];
1553         else
1554             memcpy(data + position, str->m_data16, lengthToInsert * sizeof(UChar));
1555     }
1556     if (is8Bit()) {
1557         for (unsigned i = 0; i < length() - position - lengthToReplace; ++i)
1558             data[i + position + lengthToInsert] = m_data8[i + position + lengthToReplace];
1559     } else {
1560         memcpy(data + position + lengthToInsert, characters16() + position + lengthToReplace,
1561             (length() - position - lengthToReplace) * sizeof(UChar));
1562     }
1563     return newImpl;
1564 }
1565
1566 Ref<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
1567 {
1568     if (!replacement)
1569         return *this;
1570
1571     if (replacement->is8Bit())
1572         return replace(pattern, replacement->m_data8, replacement->length());
1573
1574     return replace(pattern, replacement->m_data16, replacement->length());
1575 }
1576
1577 Ref<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength)
1578 {
1579     ASSERT(replacement);
1580
1581     size_t srcSegmentStart = 0;
1582     unsigned matchCount = 0;
1583
1584     // Count the matches.
1585     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1586         ++matchCount;
1587         ++srcSegmentStart;
1588     }
1589
1590     // If we have 0 matches then we don't have to do any more work.
1591     if (!matchCount)
1592         return *this;
1593
1594     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1595         CRASH();
1596
1597     unsigned replaceSize = matchCount * repStrLength;
1598     unsigned newSize = m_length - matchCount;
1599     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1600         CRASH();
1601
1602     newSize += replaceSize;
1603
1604     // Construct the new data.
1605     size_t srcSegmentEnd;
1606     unsigned srcSegmentLength;
1607     srcSegmentStart = 0;
1608     unsigned dstOffset = 0;
1609
1610     if (is8Bit()) {
1611         LChar* data;
1612         auto newImpl = createUninitialized(newSize, data);
1613
1614         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1615             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1616             memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1617             dstOffset += srcSegmentLength;
1618             memcpy(data + dstOffset, replacement, repStrLength * sizeof(LChar));
1619             dstOffset += repStrLength;
1620             srcSegmentStart = srcSegmentEnd + 1;
1621         }
1622
1623         srcSegmentLength = m_length - srcSegmentStart;
1624         memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1625
1626         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1627
1628         return newImpl;
1629     }
1630
1631     UChar* data;
1632     auto newImpl = createUninitialized(newSize, data);
1633
1634     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1635         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1636         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1637
1638         dstOffset += srcSegmentLength;
1639         for (unsigned i = 0; i < repStrLength; ++i)
1640             data[i + dstOffset] = replacement[i];
1641
1642         dstOffset += repStrLength;
1643         srcSegmentStart = srcSegmentEnd + 1;
1644     }
1645
1646     srcSegmentLength = m_length - srcSegmentStart;
1647     memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1648
1649     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1650
1651     return newImpl;
1652 }
1653
1654 Ref<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength)
1655 {
1656     ASSERT(replacement);
1657
1658     size_t srcSegmentStart = 0;
1659     unsigned matchCount = 0;
1660
1661     // Count the matches.
1662     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1663         ++matchCount;
1664         ++srcSegmentStart;
1665     }
1666
1667     // If we have 0 matches then we don't have to do any more work.
1668     if (!matchCount)
1669         return *this;
1670
1671     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1672         CRASH();
1673
1674     unsigned replaceSize = matchCount * repStrLength;
1675     unsigned newSize = m_length - matchCount;
1676     if (newSize >= (std::numeric_limits<unsigned>::max() - replaceSize))
1677         CRASH();
1678
1679     newSize += replaceSize;
1680
1681     // Construct the new data.
1682     size_t srcSegmentEnd;
1683     unsigned srcSegmentLength;
1684     srcSegmentStart = 0;
1685     unsigned dstOffset = 0;
1686
1687     if (is8Bit()) {
1688         UChar* data;
1689         auto newImpl = createUninitialized(newSize, data);
1690
1691         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1692             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1693             for (unsigned i = 0; i < srcSegmentLength; ++i)
1694                 data[i + dstOffset] = m_data8[i + srcSegmentStart];
1695
1696             dstOffset += srcSegmentLength;
1697             memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));
1698
1699             dstOffset += repStrLength;
1700             srcSegmentStart = srcSegmentEnd + 1;
1701         }
1702
1703         srcSegmentLength = m_length - srcSegmentStart;
1704         for (unsigned i = 0; i < srcSegmentLength; ++i)
1705             data[i + dstOffset] = m_data8[i + srcSegmentStart];
1706
1707         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1708
1709         return newImpl;
1710     }
1711
1712     UChar* data;
1713     auto newImpl = createUninitialized(newSize, data);
1714
1715     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1716         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1717         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1718
1719         dstOffset += srcSegmentLength;
1720         memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));
1721
1722         dstOffset += repStrLength;
1723         srcSegmentStart = srcSegmentEnd + 1;
1724     }
1725
1726     srcSegmentLength = m_length - srcSegmentStart;
1727     memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1728
1729     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1730
1731     return newImpl;
1732 }
1733
1734 Ref<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
1735 {
1736     if (!pattern || !replacement)
1737         return *this;
1738
1739     unsigned patternLength = pattern->length();
1740     if (!patternLength)
1741         return *this;
1742         
1743     unsigned repStrLength = replacement->length();
1744     size_t srcSegmentStart = 0;
1745     unsigned matchCount = 0;
1746     
1747     // Count the matches.
1748     while ((srcSegmentStart = find(pattern, srcSegmentStart)) != notFound) {
1749         ++matchCount;
1750         srcSegmentStart += patternLength;
1751     }
1752     
1753     // If we have 0 matches, we don't have to do any more work
1754     if (!matchCount)
1755         return *this;
1756     
1757     unsigned newSize = m_length - matchCount * patternLength;
1758     if (repStrLength && matchCount > std::numeric_limits<unsigned>::max() / repStrLength)
1759         CRASH();
1760
1761     if (newSize > (std::numeric_limits<unsigned>::max() - matchCount * repStrLength))
1762         CRASH();
1763
1764     newSize += matchCount * repStrLength;
1765
1766     
1767     // Construct the new data
1768     size_t srcSegmentEnd;
1769     unsigned srcSegmentLength;
1770     srcSegmentStart = 0;
1771     unsigned dstOffset = 0;
1772     bool srcIs8Bit = is8Bit();
1773     bool replacementIs8Bit = replacement->is8Bit();
1774     
1775     // There are 4 cases:
1776     // 1. This and replacement are both 8 bit.
1777     // 2. This and replacement are both 16 bit.
1778     // 3. This is 8 bit and replacement is 16 bit.
1779     // 4. This is 16 bit and replacement is 8 bit.
1780     if (srcIs8Bit && replacementIs8Bit) {
1781         // Case 1
1782         LChar* data;
1783         auto newImpl = createUninitialized(newSize, data);
1784         while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1785             srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1786             memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1787             dstOffset += srcSegmentLength;
1788             memcpy(data + dstOffset, replacement->m_data8, repStrLength * sizeof(LChar));
1789             dstOffset += repStrLength;
1790             srcSegmentStart = srcSegmentEnd + patternLength;
1791         }
1792
1793         srcSegmentLength = m_length - srcSegmentStart;
1794         memcpy(data + dstOffset, m_data8 + srcSegmentStart, srcSegmentLength * sizeof(LChar));
1795
1796         ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1797
1798         return newImpl;
1799     }
1800
1801     UChar* data;
1802     auto newImpl = createUninitialized(newSize, data);
1803     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != notFound) {
1804         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
1805         if (srcIs8Bit) {
1806             // Case 3.
1807             for (unsigned i = 0; i < srcSegmentLength; ++i)
1808                 data[i + dstOffset] = m_data8[i + srcSegmentStart];
1809         } else {
1810             // Case 2 & 4.
1811             memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1812         }
1813         dstOffset += srcSegmentLength;
1814         if (replacementIs8Bit) {
1815             // Cases 2 & 3.
1816             for (unsigned i = 0; i < repStrLength; ++i)
1817                 data[i + dstOffset] = replacement->m_data8[i];
1818         } else {
1819             // Case 4
1820             memcpy(data + dstOffset, replacement->m_data16, repStrLength * sizeof(UChar));
1821         }
1822         dstOffset += repStrLength;
1823         srcSegmentStart = srcSegmentEnd + patternLength;
1824     }
1825
1826     srcSegmentLength = m_length - srcSegmentStart;
1827     if (srcIs8Bit) {
1828         // Case 3.
1829         for (unsigned i = 0; i < srcSegmentLength; ++i)
1830             data[i + dstOffset] = m_data8[i + srcSegmentStart];
1831     } else {
1832         // Cases 2 & 4.
1833         memcpy(data + dstOffset, m_data16 + srcSegmentStart, srcSegmentLength * sizeof(UChar));
1834     }
1835
1836     ASSERT(dstOffset + srcSegmentLength == newImpl.get().length());
1837
1838     return newImpl;
1839 }
1840
1841 bool equal(const StringImpl* a, const StringImpl* b)
1842 {
1843     return equalCommon(a, b);
1844 }
1845
1846 template <typename CharType>
1847 inline bool equalInternal(const StringImpl* a, const CharType* b, unsigned length)
1848 {
1849     if (!a)
1850         return !b;
1851     if (!b)
1852         return false;
1853
1854     if (a->length() != length)
1855         return false;
1856     if (a->is8Bit())
1857         return equal(a->characters8(), b, length);
1858     return equal(a->characters16(), b, length);
1859 }
1860
1861 bool equal(const StringImpl* a, const LChar* b, unsigned length)
1862 {
1863     return equalInternal(a, b, length);
1864 }
1865
1866 bool equal(const StringImpl* a, const UChar* b, unsigned length)
1867 {
1868     return equalInternal(a, b, length);
1869 }
1870
1871 bool equal(const StringImpl* a, const LChar* b)
1872 {
1873     if (!a)
1874         return !b;
1875     if (!b)
1876         return !a;
1877
1878     unsigned length = a->length();
1879
1880     if (a->is8Bit()) {
1881         const LChar* aPtr = a->characters8();
1882         for (unsigned i = 0; i != length; ++i) {
1883             LChar bc = b[i];
1884             LChar ac = aPtr[i];
1885             if (!bc)
1886                 return false;
1887             if (ac != bc)
1888                 return false;
1889         }
1890
1891         return !b[length];
1892     }
1893
1894     const UChar* aPtr = a->characters16();
1895     for (unsigned i = 0; i != length; ++i) {
1896         LChar bc = b[i];
1897         if (!bc)
1898             return false;
1899         if (aPtr[i] != bc)
1900             return false;
1901     }
1902
1903     return !b[length];
1904 }
1905
1906 bool equal(const StringImpl& a, const StringImpl& b)
1907 {
1908     return equalCommon(a, b);
1909 }
1910
1911 bool equalIgnoringCase(const StringImpl* a, const StringImpl* b)
1912 {
1913     if (a == b)
1914         return true;
1915     if (!a || !b)
1916         return false;
1917
1918     return CaseFoldingHash::equal(a, b);
1919 }
1920
1921 bool equalIgnoringCase(const StringImpl* a, const LChar* b)
1922 {
1923     if (!a)
1924         return !b;
1925     if (!b)
1926         return !a;
1927
1928     unsigned length = a->length();
1929
1930     // Do a faster loop for the case where all the characters are ASCII.
1931     UChar ored = 0;
1932     bool equal = true;
1933     if (a->is8Bit()) {
1934         const LChar* as = a->characters8();
1935         for (unsigned i = 0; i != length; ++i) {
1936             LChar bc = b[i];
1937             if (!bc)
1938                 return false;
1939             UChar ac = as[i];
1940             ored |= ac;
1941             equal = equal && (toASCIILower(ac) == toASCIILower(bc));
1942         }
1943         
1944         // Do a slower implementation for cases that include non-ASCII characters.
1945         if (ored & ~0x7F) {
1946             equal = true;
1947             for (unsigned i = 0; i != length; ++i)
1948                 equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
1949         }
1950         
1951         return equal && !b[length];        
1952     }
1953
1954     const UChar* as = a->characters16();
1955     for (unsigned i = 0; i != length; ++i) {
1956         LChar bc = b[i];
1957         if (!bc)
1958             return false;
1959         UChar ac = as[i];
1960         ored |= ac;
1961         equal = equal && (toASCIILower(ac) == toASCIILower(bc));
1962     }
1963
1964     // Do a slower implementation for cases that include non-ASCII characters.
1965     if (ored & ~0x7F) {
1966         equal = true;
1967         for (unsigned i = 0; i != length; ++i) {
1968             equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT);
1969         }
1970     }
1971
1972     return equal && !b[length];
1973 }
1974
1975 bool equalIgnoringCaseNonNull(const StringImpl* a, const StringImpl* b)
1976 {
1977     ASSERT(a && b);
1978     if (a == b)
1979         return true;
1980
1981     unsigned length = a->length();
1982     if (length != b->length())
1983         return false;
1984
1985     if (a->is8Bit()) {
1986         if (b->is8Bit())
1987             return equalIgnoringCase(a->characters8(), b->characters8(), length);
1988
1989         return equalIgnoringCase(b->characters16(), a->characters8(), length);
1990     }
1991
1992     if (b->is8Bit())
1993         return equalIgnoringCase(a->characters16(), b->characters8(), length);
1994
1995     return equalIgnoringCase(a->characters16(), b->characters16(), length);
1996 }
1997
1998 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
1999 {
2000     if (!a && b && !b->length())
2001         return true;
2002     if (!b && a && !a->length())
2003         return true;
2004     return equal(a, b);
2005 }
2006
2007 bool equalIgnoringASCIICase(const StringImpl& a, const StringImpl& b)
2008 {
2009     return equalIgnoringASCIICaseCommon(a, b);
2010 }
2011
2012 bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl*b)
2013 {
2014     if (a == b)
2015         return true;
2016     if (!a || !b)
2017         return false;
2018     return equalIgnoringASCIICaseCommon(*a, *b);
2019 }
2020
2021 bool equalIgnoringASCIICase(const StringImpl& a, const char* b, unsigned bLength)
2022 {
2023     if (bLength != a.length())
2024         return false;
2025
2026     if (a.is8Bit())
2027         return equalIgnoringASCIICase(a.characters8(), b, bLength);
2028
2029     return equalIgnoringASCIICase(a.characters16(), b, bLength);
2030 }
2031
2032 bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b)
2033 {
2034     ASSERT(a);
2035     ASSERT(b);
2036     return equalIgnoringASCIICaseCommon(*a, *b);
2037 }
2038
2039 UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality)
2040 {
2041     for (unsigned i = 0; i < m_length; ++i) {
2042         UCharDirection charDirection = u_charDirection(is8Bit() ? m_data8[i] : m_data16[i]);
2043         if (charDirection == U_LEFT_TO_RIGHT) {
2044             if (hasStrongDirectionality)
2045                 *hasStrongDirectionality = true;
2046             return U_LEFT_TO_RIGHT;
2047         }
2048         if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
2049             if (hasStrongDirectionality)
2050                 *hasStrongDirectionality = true;
2051             return U_RIGHT_TO_LEFT;
2052         }
2053     }
2054     if (hasStrongDirectionality)
2055         *hasStrongDirectionality = false;
2056     return U_LEFT_TO_RIGHT;
2057 }
2058
2059 Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>& buffer)
2060 {
2061     unsigned length = buffer.length();
2062     if (!length)
2063         return *empty();
2064     return adoptRef(*new StringImpl(buffer.release(), length));
2065 }
2066
2067 Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>& buffer)
2068 {
2069     unsigned length = buffer.length();
2070     if (!length)
2071         return *empty();
2072     return adoptRef(*new StringImpl(buffer.release(), length));
2073 }
2074
2075 size_t StringImpl::sizeInBytes() const
2076 {
2077     // FIXME: support substrings
2078     size_t size = length();
2079     if (!is8Bit())
2080         size *= 2;
2081     return size + sizeof(*this);
2082 }
2083
2084 // Helper to write a three-byte UTF-8 code point to the buffer, caller must check room is available.
2085 static inline void putUTF8Triple(char*& buffer, UChar ch)
2086 {
2087     ASSERT(ch >= 0x0800);
2088     *buffer++ = static_cast<char>(((ch >> 12) & 0x0F) | 0xE0);
2089     *buffer++ = static_cast<char>(((ch >> 6) & 0x3F) | 0x80);
2090     *buffer++ = static_cast<char>((ch & 0x3F) | 0x80);
2091 }
2092
2093 bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode)
2094 {
2095     if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) {
2096         const UChar* charactersEnd = characters + length;
2097         char* bufferEnd = buffer + bufferSize;
2098         while (characters < charactersEnd) {
2099             // Use strict conversion to detect unpaired surrogates.
2100             ConversionResult result = convertUTF16ToUTF8(&characters, charactersEnd, &buffer, bufferEnd, true);
2101             ASSERT(result != targetExhausted);
2102             // Conversion fails when there is an unpaired surrogate.
2103             // Put replacement character (U+FFFD) instead of the unpaired surrogate.
2104             if (result != conversionOK) {
2105                 ASSERT((0xD800 <= *characters && *characters <= 0xDFFF));
2106                 // There should be room left, since one UChar hasn't been converted.
2107                 ASSERT((buffer + 3) <= bufferEnd);
2108                 putUTF8Triple(buffer, replacementCharacter);
2109                 ++characters;
2110             }
2111         }
2112     } else {
2113         bool strict = mode == StrictConversion;
2114         const UChar* originalCharacters = characters;
2115         ConversionResult result = convertUTF16ToUTF8(&characters, characters + length, &buffer, buffer + bufferSize, strict);
2116         ASSERT(result != targetExhausted); // (length * 3) should be sufficient for any conversion
2117
2118         // Only produced from strict conversion.
2119         if (result == sourceIllegal) {
2120             ASSERT(strict);
2121             return false;
2122         }
2123
2124         // Check for an unconverted high surrogate.
2125         if (result == sourceExhausted) {
2126             if (strict)
2127                 return false;
2128             // This should be one unpaired high surrogate. Treat it the same
2129             // was as an unpaired high surrogate would have been handled in
2130             // the middle of a string with non-strict conversion - which is
2131             // to say, simply encode it to UTF-8.
2132             ASSERT_UNUSED(
2133                 originalCharacters, (characters + 1) == (originalCharacters + length));
2134             ASSERT((*characters >= 0xD800) && (*characters <= 0xDBFF));
2135             // There should be room left, since one UChar hasn't been converted.
2136             ASSERT((buffer + 3) <= (buffer + bufferSize));
2137             putUTF8Triple(buffer, *characters);
2138         }
2139     }
2140     
2141     return true;
2142 }
2143
2144 CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length)
2145 {
2146     if (!length)
2147         return CString("", 0);
2148     if (length > std::numeric_limits<unsigned>::max() / 3)
2149         return CString();
2150     Vector<char, 1024> bufferVector(length * 3);
2151     char* buffer = bufferVector.data();
2152     const LChar* source = characters;
2153     ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size());
2154     ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2155     return CString(bufferVector.data(), buffer - bufferVector.data());
2156 }
2157
2158 CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode)
2159 {
2160     if (!length)
2161         return CString("", 0);
2162     if (length > std::numeric_limits<unsigned>::max() / 3)
2163         return CString();
2164     Vector<char, 1024> bufferVector(length * 3);
2165     char* buffer = bufferVector.data();
2166     if (!utf8Impl(characters, length, buffer, bufferVector.size(), mode))
2167         return CString();
2168     return CString(bufferVector.data(), buffer - bufferVector.data());
2169 }
2170
2171 CString StringImpl::utf8ForRange(unsigned offset, unsigned length, ConversionMode mode) const
2172 {
2173     ASSERT(offset <= this->length());
2174     ASSERT(offset + length <= this->length());
2175     
2176     if (!length)
2177         return CString("", 0);
2178
2179     // Allocate a buffer big enough to hold all the characters
2180     // (an individual UTF-16 UChar can only expand to 3 UTF-8 bytes).
2181     // Optimization ideas, if we find this function is hot:
2182     //  * We could speculatively create a CStringBuffer to contain 'length' 
2183     //    characters, and resize if necessary (i.e. if the buffer contains
2184     //    non-ascii characters). (Alternatively, scan the buffer first for
2185     //    ascii characters, so we know this will be sufficient).
2186     //  * We could allocate a CStringBuffer with an appropriate size to
2187     //    have a good chance of being able to write the string into the
2188     //    buffer without reallocing (say, 1.5 x length).
2189     if (length > std::numeric_limits<unsigned>::max() / 3)
2190         return CString();
2191     Vector<char, 1024> bufferVector(length * 3);
2192
2193     char* buffer = bufferVector.data();
2194
2195     if (is8Bit()) {
2196         const LChar* characters = this->characters8() + offset;
2197
2198         ConversionResult result = convertLatin1ToUTF8(&characters, characters + length, &buffer, buffer + bufferVector.size());
2199         ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion
2200     } else {
2201         if (!utf8Impl(this->characters16() + offset, length, buffer, bufferVector.size(), mode))
2202             return CString();
2203     }
2204
2205     return CString(bufferVector.data(), buffer - bufferVector.data());
2206 }
2207
2208 CString StringImpl::utf8(ConversionMode mode) const
2209 {
2210     return utf8ForRange(0, length(), mode);
2211 }
2212
2213 // Table is based on ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
2214 const UChar StringImpl::latin1CaseFoldTable[256] = {
2215     0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
2216     0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, 
2217     0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, 
2218     0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f,
2219     0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2220     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f,
2221     0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f,
2222     0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f,
2223     0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f,
2224     0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f,
2225     0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, 0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af,
2226     0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x03bc, 0x00b6, 0x00b7, 0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf,
2227     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2228     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00d7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00df,
2229     0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef,
2230     0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff, 
2231 };
2232
2233 bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b)
2234 {
2235     if (!b)
2236         return !aLength;
2237     if (aLength != b->length())
2238         return false;
2239     if (b->is8Bit()) {
2240         const LChar* bCharacters = b->characters8();
2241         for (unsigned i = 0; i < aLength; ++i) {
2242             if (a[i] != bCharacters[i])
2243                 return false;
2244         }
2245         return true;
2246     }
2247     return !memcmp(a, b->characters16(), b->length() * sizeof(UChar));
2248 }
2249
2250 } // namespace WTF