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