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