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