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 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/StdLibExtras.h>

    32 #include <wtf/WTFThreadData.h>

    33 

    34 using namespace WTF;

    35 using namespace Unicode;

    36 

    37 namespace WebCore {

    38 

    39 static const unsigned minLengthToShare = 20;

    40 

    41 COMPILE_ASSERT(sizeof(StringImpl) == 2 * sizeof(int) + 3 * sizeof(void*), StringImpl_should_stay_small);

    42 

    43 StringImpl::~StringImpl()

    44 {

    45     ASSERT(!isStatic());

    46 

    47     if (isAtomic())

    48         AtomicString::remove(this);

    49 #if USE(JSC)

    50     if (isIdentifier())

    51         wtfThreadData().currentIdentifierTable()->remove(this);

    52 #endif

    53 

    54     BufferOwnership ownership = bufferOwnership();

    55     if (ownership != BufferInternal) {

    56         if (ownership == BufferOwned) {

    57             ASSERT(!m_sharedBuffer);

    58             ASSERT(m_data);

    59             fastFree(const_cast<UChar*>(m_data));

    60         } else if (ownership == BufferSubstring) {

    61             ASSERT(m_substringBuffer);

    62             m_substringBuffer->deref();

    63         } else {

    64             ASSERT(ownership == BufferShared);

    65             ASSERT(m_sharedBuffer);

    66             m_sharedBuffer->deref();

    67         }

    68     }

    69 }

    70 

    71 PassRefPtr<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data)

    72 {

    73     if (!length) {

    74         data = 0;

    75         return empty();

    76     }

    77 

    78     // Allocate a single buffer large enough to contain the StringImpl

    79     // struct as well as the data which it contains. This removes one 

    80     // heap allocation from this call.

    81     if (length > ((std::numeric_limits<size_t>::max() - sizeof(StringImpl)) / sizeof(UChar)))

    82         CRASH();

    83     size_t size = sizeof(StringImpl) + length * sizeof(UChar);

    84     StringImpl* string = static_cast<StringImpl*>(fastMalloc(size));

    85 

    86     data = reinterpret_cast<UChar*>(string + 1);

    87     return adoptRef(new (string) StringImpl(length));

    88 }

    89 

    90 PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length)

    91 {

    92     if (!characters || !length)

    93         return empty();

    94 

    95     UChar* data;

    96     PassRefPtr<StringImpl> string = createUninitialized(length, data);

    97     memcpy(data, characters, length * sizeof(UChar));

    98     return string;

    99 }

   100 

   101 PassRefPtr<StringImpl> StringImpl::create(const char* characters, unsigned length)

   102 {

   103     if (!characters || !length)

   104         return empty();

   105 

   106     UChar* data;

   107     PassRefPtr<StringImpl> string = createUninitialized(length, data);

   108     for (unsigned i = 0; i != length; ++i) {

   109         unsigned char c = characters[i];

   110         data[i] = c;

   111     }

   112     return string;

   113 }

   114 

   115 PassRefPtr<StringImpl> StringImpl::create(const char* string)

   116 {

   117     if (!string)

   118         return empty();

   119     return create(string, strlen(string));

   120 }

   121 

   122 PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)

   123 {

   124     ASSERT(characters);

   125     ASSERT(minLengthToShare && length >= minLengthToShare);

   126     return adoptRef(new StringImpl(characters, length, sharedBuffer));

   127 }

   128 

   129 SharedUChar* StringImpl::sharedBuffer()

   130 {

   131     if (m_length < minLengthToShare)

   132         return 0;

   133     // All static strings are smaller that the minimim length to share.

   134     ASSERT(!isStatic());

   135 

   136     BufferOwnership ownership = bufferOwnership();

   137 

   138     if (ownership == BufferInternal)

   139         return 0;

   140     if (ownership == BufferSubstring)

   141         return m_substringBuffer->sharedBuffer();

   142     if (ownership == BufferOwned) {

   143         ASSERT(!m_sharedBuffer);

   144         m_sharedBuffer = SharedUChar::create(new SharableUChar(m_data)).releaseRef();

   145         m_refCountAndFlags = (m_refCountAndFlags & ~s_refCountMaskBufferOwnership) | BufferShared;

   146     }

   147 

   148     ASSERT(bufferOwnership() == BufferShared);

   149     ASSERT(m_sharedBuffer);

   150     return m_sharedBuffer;

   151 }

   152 

   153 bool StringImpl::containsOnlyWhitespace()

   154 {

   155     // FIXME: The definition of whitespace here includes a number of characters

   156     // that are not whitespace from the point of view of RenderText; I wonder if

   157     // that's a problem in practice.

   158     for (unsigned i = 0; i < m_length; i++)

   159         if (!isASCIISpace(m_data[i]))

   160             return false;

   161     return true;

   162 }

   163 

   164 PassRefPtr<StringImpl> StringImpl::substring(unsigned start, unsigned length)

   165 {

   166     if (start >= m_length)

   167         return empty();

   168     unsigned maxLength = m_length - start;

   169     if (length >= maxLength) {

   170         if (!start)

   171             return this;

   172         length = maxLength;

   173     }

   174     return create(m_data + start, length);

   175 }

   176 

   177 UChar32 StringImpl::characterStartingAt(unsigned i)

   178 {

   179     if (U16_IS_SINGLE(m_data[i]))

   180         return m_data[i];

   181     if (i + 1 < m_length && U16_IS_LEAD(m_data[i]) && U16_IS_TRAIL(m_data[i + 1]))

   182         return U16_GET_SUPPLEMENTARY(m_data[i], m_data[i + 1]);

   183     return 0;

   184 }

   185 

   186 PassRefPtr<StringImpl> StringImpl::lower()

   187 {

   188     // Note: This is a hot function in the Dromaeo benchmark, specifically the

   189     // no-op code path up through the first 'return' statement.

   190     

   191     // First scan the string for uppercase and non-ASCII characters:

   192     UChar ored = 0;

   193     bool noUpper = true;

   194     const UChar *end = m_data + m_length;

   195     for (const UChar* chp = m_data; chp != end; chp++) {

   196         if (UNLIKELY(isASCIIUpper(*chp)))

   197             noUpper = false;

   198         ored |= *chp;

   199     }

   200     

   201     // Nothing to do if the string is all ASCII with no uppercase.

   202     if (noUpper && !(ored & ~0x7F))

   203         return this;

   204 

   205     int32_t length = m_length;

   206     UChar* data;

   207     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

   208 

   209     if (!(ored & ~0x7F)) {

   210         // Do a faster loop for the case where all the characters are ASCII.

   211         for (int i = 0; i < length; i++) {

   212             UChar c = m_data[i];

   213             data[i] = toASCIILower(c);

   214         }

   215         return newImpl;

   216     }

   217     

   218     // Do a slower implementation for cases that include non-ASCII characters.

   219     bool error;

   220     int32_t realLength = Unicode::toLower(data, length, m_data, m_length, &error);

   221     if (!error && realLength == length)

   222         return newImpl;

   223     newImpl = createUninitialized(realLength, data);

   224     Unicode::toLower(data, realLength, m_data, m_length, &error);

   225     if (error)

   226         return this;

   227     return newImpl;

   228 }

   229 

   230 PassRefPtr<StringImpl> StringImpl::upper()

   231 {

   232     // This function could be optimized for no-op cases the way lower() is,

   233     // but in empirical testing, few actual calls to upper() are no-ops, so

   234     // it wouldn't be worth the extra time for pre-scanning.

   235     UChar* data;

   236     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

   237     int32_t length = m_length;

   238 

   239     // Do a faster loop for the case where all the characters are ASCII.

   240     UChar ored = 0;

   241     for (int i = 0; i < length; i++) {

   242         UChar c = m_data[i];

   243         ored |= c;

   244         data[i] = toASCIIUpper(c);

   245     }

   246     if (!(ored & ~0x7F))

   247         return newImpl;

   248 

   249     // Do a slower implementation for cases that include non-ASCII characters.

   250     bool error;

   251     int32_t realLength = Unicode::toUpper(data, length, m_data, m_length, &error);

   252     if (!error && realLength == length)

   253         return newImpl;

   254     newImpl = createUninitialized(realLength, data);

   255     Unicode::toUpper(data, realLength, m_data, m_length, &error);

   256     if (error)

   257         return this;

   258     return newImpl;

   259 }

   260 

   261 PassRefPtr<StringImpl> StringImpl::secure(UChar aChar)

   262 {

   263     UChar* data;

   264     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

   265     int32_t length = m_length;

   266     for (int i = 0; i < length; ++i)

   267         data[i] = aChar;

   268     return newImpl;

   269 }

   270 

   271 PassRefPtr<StringImpl> StringImpl::foldCase()

   272 {

   273     UChar* data;

   274     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

   275     int32_t length = m_length;

   276 

   277     // Do a faster loop for the case where all the characters are ASCII.

   278     UChar ored = 0;

   279     for (int i = 0; i < length; i++) {

   280         UChar c = m_data[i];

   281         ored |= c;

   282         data[i] = toASCIILower(c);

   283     }

   284     if (!(ored & ~0x7F))

   285         return newImpl;

   286 

   287     // Do a slower implementation for cases that include non-ASCII characters.

   288     bool error;

   289     int32_t realLength = Unicode::foldCase(data, length, m_data, m_length, &error);

   290     if (!error && realLength == length)

   291         return newImpl;

   292     newImpl = createUninitialized(realLength, data);

   293     Unicode::foldCase(data, realLength, m_data, m_length, &error);

   294     if (error)

   295         return this;

   296     return newImpl;

   297 }

   298 

   299 PassRefPtr<StringImpl> StringImpl::stripWhiteSpace()

   300 {

   301     if (!m_length)

   302         return empty();

   303 

   304     unsigned start = 0;

   305     unsigned end = m_length - 1;

   306     

   307     // skip white space from start

   308     while (start <= end && isSpaceOrNewline(m_data[start]))

   309         start++;

   310     

   311     // only white space

   312     if (start > end) 

   313         return empty();

   314 

   315     // skip white space from end

   316     while (end && isSpaceOrNewline(m_data[end]))

   317         end--;

   318 

   319     if (!start && end == m_length - 1)

   320         return this;

   321     return create(m_data + start, end + 1 - start);

   322 }

   323 

   324 PassRefPtr<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)

   325 {

   326     const UChar* from = m_data;

   327     const UChar* fromend = from + m_length;

   328 

   329     // Assume the common case will not remove any characters

   330     while (from != fromend && !findMatch(*from))

   331         from++;

   332     if (from == fromend)

   333         return this;

   334 

   335     StringBuffer data(m_length);

   336     UChar* to = data.characters();

   337     unsigned outc = from - m_data;

   338 

   339     if (outc)

   340         memcpy(to, m_data, outc * sizeof(UChar));

   341 

   342     while (true) {

   343         while (from != fromend && findMatch(*from))

   344             from++;

   345         while (from != fromend && !findMatch(*from))

   346             to[outc++] = *from++;

   347         if (from == fromend)

   348             break;

   349     }

   350 

   351     data.shrink(outc);

   352 

   353     return adopt(data);

   354 }

   355 

   356 PassRefPtr<StringImpl> StringImpl::simplifyWhiteSpace()

   357 {

   358     StringBuffer data(m_length);

   359 

   360     const UChar* from = m_data;

   361     const UChar* fromend = from + m_length;

   362     int outc = 0;

   363     bool changedToSpace = false;

   364     

   365     UChar* to = data.characters();

   366     

   367     while (true) {

   368         while (from != fromend && isSpaceOrNewline(*from)) {

   369             if (*from != ' ')

   370                 changedToSpace = true;

   371             from++;

   372         }

   373         while (from != fromend && !isSpaceOrNewline(*from))

   374             to[outc++] = *from++;

   375         if (from != fromend)

   376             to[outc++] = ' ';

   377         else

   378             break;

   379     }

   380     

   381     if (outc > 0 && to[outc - 1] == ' ')

   382         outc--;

   383     

   384     if (static_cast<unsigned>(outc) == m_length && !changedToSpace)

   385         return this;

   386     

   387     data.shrink(outc);

   388     

   389     return adopt(data);

   390 }

   391 

   392 int StringImpl::toIntStrict(bool* ok, int base)

   393 {

   394     return charactersToIntStrict(m_data, m_length, ok, base);

   395 }

   396 

   397 unsigned StringImpl::toUIntStrict(bool* ok, int base)

   398 {

   399     return charactersToUIntStrict(m_data, m_length, ok, base);

   400 }

   401 

   402 int64_t StringImpl::toInt64Strict(bool* ok, int base)

   403 {

   404     return charactersToInt64Strict(m_data, m_length, ok, base);

   405 }

   406 

   407 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)

   408 {

   409     return charactersToUInt64Strict(m_data, m_length, ok, base);

   410 }

   411 

   412 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)

   413 {

   414     return charactersToIntPtrStrict(m_data, m_length, ok, base);

   415 }

   416 

   417 int StringImpl::toInt(bool* ok)

   418 {

   419     return charactersToInt(m_data, m_length, ok);

   420 }

   421 

   422 unsigned StringImpl::toUInt(bool* ok)

   423 {

   424     return charactersToUInt(m_data, m_length, ok);

   425 }

   426 

   427 int64_t StringImpl::toInt64(bool* ok)

   428 {

   429     return charactersToInt64(m_data, m_length, ok);

   430 }

   431 

   432 uint64_t StringImpl::toUInt64(bool* ok)

   433 {

   434     return charactersToUInt64(m_data, m_length, ok);

   435 }

   436 

   437 intptr_t StringImpl::toIntPtr(bool* ok)

   438 {

   439     return charactersToIntPtr(m_data, m_length, ok);

   440 }

   441 

   442 double StringImpl::toDouble(bool* ok)

   443 {

   444     return charactersToDouble(m_data, m_length, ok);

   445 }

   446 

   447 float StringImpl::toFloat(bool* ok)

   448 {

   449     return charactersToFloat(m_data, m_length, ok);

   450 }

   451 

   452 static bool equal(const UChar* a, const char* b, int length)

   453 {

   454     ASSERT(length >= 0);

   455     while (length--) {

   456         unsigned char bc = *b++;

   457         if (*a++ != bc)

   458             return false;

   459     }

   460     return true;

   461 }

   462 

   463 bool equalIgnoringCase(const UChar* a, const char* b, unsigned length)

   464 {

   465     while (length--) {

   466         unsigned char bc = *b++;

   467         if (foldCase(*a++) != foldCase(bc))

   468             return false;

   469     }

   470     return true;

   471 }

   472 

   473 static inline bool equalIgnoringCase(const UChar* a, const UChar* b, int length)

   474 {

   475     ASSERT(length >= 0);

   476     return umemcasecmp(a, b, length) == 0;

   477 }

   478 

   479 int codePointCompare(const StringImpl* s1, const StringImpl* s2)

   480 {

   481     const unsigned l1 = s1 ? s1->length() : 0;

   482     const unsigned l2 = s2 ? s2->length() : 0;

   483     const unsigned lmin = l1 < l2 ? l1 : l2;

   484     const UChar* c1 = s1 ? s1->characters() : 0;

   485     const UChar* c2 = s2 ? s2->characters() : 0;

   486     unsigned pos = 0;

   487     while (pos < lmin && *c1 == *c2) {

   488         c1++;

   489         c2++;

   490         pos++;

   491     }

   492 

   493     if (pos < lmin)

   494         return (c1[0] > c2[0]) ? 1 : -1;

   495 

   496     if (l1 == l2)

   497         return 0;

   498 

   499     return (l1 > l2) ? 1 : -1;

   500 }

   501 

   502 int StringImpl::find(const char* chs, int index, bool caseSensitive)

   503 {

   504     if (!chs || index < 0)

   505         return -1;

   506 

   507     int chsLength = strlen(chs);

   508     int n = m_length - index;

   509     if (n < 0)

   510         return -1;

   511     n -= chsLength - 1;

   512     if (n <= 0)

   513         return -1;

   514 

   515     const char* chsPlusOne = chs + 1;

   516     int chsLengthMinusOne = chsLength - 1;

   517     

   518     const UChar* ptr = m_data + index - 1;

   519     if (caseSensitive) {

   520         UChar c = *chs;

   521         do {

   522             if (*++ptr == c && equal(ptr + 1, chsPlusOne, chsLengthMinusOne))

   523                 return m_length - chsLength - n + 1;

   524         } while (--n);

   525     } else {

   526         UChar lc = Unicode::foldCase(*chs);

   527         do {

   528             if (Unicode::foldCase(*++ptr) == lc && equalIgnoringCase(ptr + 1, chsPlusOne, chsLengthMinusOne))

   529                 return m_length - chsLength - n + 1;

   530         } while (--n);

   531     }

   532 

   533     return -1;

   534 }

   535 

   536 int StringImpl::find(UChar c, int start)

   537 {

   538     return WebCore::find(m_data, m_length, c, start);

   539 }

   540 

   541 int StringImpl::find(CharacterMatchFunctionPtr matchFunction, int start)

   542 {

   543     return WebCore::find(m_data, m_length, matchFunction, start);

   544 }

   545 

   546 int StringImpl::find(StringImpl* str, int index, bool caseSensitive)

   547 {

   548     /*

   549       We use a simple trick for efficiency's sake. Instead of

   550       comparing strings, we compare the sum of str with that of

   551       a part of this string. Only if that matches, we call memcmp

   552       or ucstrnicmp.

   553     */

   554     ASSERT(str);

   555     if (index < 0)

   556         index += m_length;

   557     int lstr = str->m_length;

   558     int lthis = m_length - index;

   559     if ((unsigned)lthis > m_length)

   560         return -1;

   561     int delta = lthis - lstr;

   562     if (delta < 0)

   563         return -1;

   564 

   565     const UChar* uthis = m_data + index;

   566     const UChar* ustr = str->m_data;

   567     unsigned hthis = 0;

   568     unsigned hstr = 0;

   569     if (caseSensitive) {

   570         for (int i = 0; i < lstr; i++) {

   571             hthis += uthis[i];

   572             hstr += ustr[i];

   573         }

   574         int i = 0;

   575         while (1) {

   576             if (hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(UChar)) == 0)

   577                 return index + i;

   578             if (i == delta)

   579                 return -1;

   580             hthis += uthis[i + lstr];

   581             hthis -= uthis[i];

   582             i++;

   583         }

   584     } else {

   585         for (int i = 0; i < lstr; i++ ) {

   586             hthis += toASCIILower(uthis[i]);

   587             hstr += toASCIILower(ustr[i]);

   588         }

   589         int i = 0;

   590         while (1) {

   591             if (hthis == hstr && equalIgnoringCase(uthis + i, ustr, lstr))

   592                 return index + i;

   593             if (i == delta)

   594                 return -1;

   595             hthis += toASCIILower(uthis[i + lstr]);

   596             hthis -= toASCIILower(uthis[i]);

   597             i++;

   598         }

   599     }

   600 }

   601 

   602 int StringImpl::reverseFind(UChar c, int index)

   603 {

   604     return WebCore::reverseFind(m_data, m_length, c, index);

   605 }

   606 

   607 int StringImpl::reverseFind(StringImpl* str, int index, bool caseSensitive)

   608 {

   609     /*

   610      See StringImpl::find() for explanations.

   611      */

   612     ASSERT(str);

   613     int lthis = m_length;

   614     if (index < 0)

   615         index += lthis;

   616     

   617     int lstr = str->m_length;

   618     int delta = lthis - lstr;

   619     if ( index < 0 || index > lthis || delta < 0 )

   620         return -1;

   621     if ( index > delta )

   622         index = delta;

   623     

   624     const UChar *uthis = m_data;

   625     const UChar *ustr = str->m_data;

   626     unsigned hthis = 0;

   627     unsigned hstr = 0;

   628     int i;

   629     if (caseSensitive) {

   630         for ( i = 0; i < lstr; i++ ) {

   631             hthis += uthis[index + i];

   632             hstr += ustr[i];

   633         }

   634         i = index;

   635         while (1) {

   636             if (hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(UChar)) == 0)

   637                 return i;

   638             if (i == 0)

   639                 return -1;

   640             i--;

   641             hthis -= uthis[i + lstr];

   642             hthis += uthis[i];

   643         }

   644     } else {

   645         for (i = 0; i < lstr; i++) {

   646             hthis += toASCIILower(uthis[index + i]);

   647             hstr += toASCIILower(ustr[i]);

   648         }

   649         i = index;

   650         while (1) {

   651             if (hthis == hstr && equalIgnoringCase(uthis + i, ustr, lstr) )

   652                 return i;

   653             if (i == 0)

   654                 return -1;

   655             i--;

   656             hthis -= toASCIILower(uthis[i + lstr]);

   657             hthis += toASCIILower(uthis[i]);

   658         }

   659     }

   660     

   661     // Should never get here.

   662     return -1;

   663 }

   664 

   665 bool StringImpl::endsWith(StringImpl* m_data, bool caseSensitive)

   666 {

   667     ASSERT(m_data);

   668     int start = m_length - m_data->m_length;

   669     if (start >= 0)

   670         return (find(m_data, start, caseSensitive) == start);

   671     return false;

   672 }

   673 

   674 PassRefPtr<StringImpl> StringImpl::replace(UChar oldC, UChar newC)

   675 {

   676     if (oldC == newC)

   677         return this;

   678     unsigned i;

   679     for (i = 0; i != m_length; ++i)

   680         if (m_data[i] == oldC)

   681             break;

   682     if (i == m_length)

   683         return this;

   684 

   685     UChar* data;

   686     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

   687 

   688     for (i = 0; i != m_length; ++i) {

   689         UChar ch = m_data[i];

   690         if (ch == oldC)

   691             ch = newC;

   692         data[i] = ch;

   693     }

   694     return newImpl;

   695 }

   696 

   697 PassRefPtr<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str)

   698 {

   699     position = min(position, length());

   700     lengthToReplace = min(lengthToReplace, length() - position);

   701     unsigned lengthToInsert = str ? str->length() : 0;

   702     if (!lengthToReplace && !lengthToInsert)

   703         return this;

   704     UChar* data;

   705     PassRefPtr<StringImpl> newImpl =

   706         createUninitialized(length() - lengthToReplace + lengthToInsert, data);

   707     memcpy(data, characters(), position * sizeof(UChar));

   708     if (str)

   709         memcpy(data + position, str->characters(), lengthToInsert * sizeof(UChar));

   710     memcpy(data + position + lengthToInsert, characters() + position + lengthToReplace,

   711         (length() - position - lengthToReplace) * sizeof(UChar));

   712     return newImpl;

   713 }

   714 

   715 PassRefPtr<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)

   716 {

   717     if (!replacement)

   718         return this;

   719         

   720     int repStrLength = replacement->length();

   721     int srcSegmentStart = 0;

   722     int matchCount = 0;

   723     

   724     // Count the matches

   725     while ((srcSegmentStart = find(pattern, srcSegmentStart)) >= 0) {

   726         ++matchCount;

   727         ++srcSegmentStart;

   728     }

   729     

   730     // If we have 0 matches, we don't have to do any more work

   731     if (!matchCount)

   732         return this;

   733     

   734     UChar* data;

   735     PassRefPtr<StringImpl> newImpl =

   736         createUninitialized(m_length - matchCount + (matchCount * repStrLength), data);

   737 

   738     // Construct the new data

   739     int srcSegmentEnd;

   740     int srcSegmentLength;

   741     srcSegmentStart = 0;

   742     int dstOffset = 0;

   743     

   744     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) >= 0) {

   745         srcSegmentLength = srcSegmentEnd - srcSegmentStart;

   746         memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));

   747         dstOffset += srcSegmentLength;

   748         memcpy(data + dstOffset, replacement->m_data, repStrLength * sizeof(UChar));

   749         dstOffset += repStrLength;

   750         srcSegmentStart = srcSegmentEnd + 1;

   751     }

   752 

   753     srcSegmentLength = m_length - srcSegmentStart;

   754     memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));

   755 

   756     ASSERT(dstOffset + srcSegmentLength == static_cast<int>(newImpl->length()));

   757 

   758     return newImpl;

   759 }

   760 

   761 PassRefPtr<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)

   762 {

   763     if (!pattern || !replacement)

   764         return this;

   765 

   766     int patternLength = pattern->length();

   767     if (!patternLength)

   768         return this;

   769         

   770     int repStrLength = replacement->length();

   771     int srcSegmentStart = 0;

   772     int matchCount = 0;

   773     

   774     // Count the matches

   775     while ((srcSegmentStart = find(pattern, srcSegmentStart)) >= 0) {

   776         ++matchCount;

   777         srcSegmentStart += patternLength;

   778     }

   779     

   780     // If we have 0 matches, we don't have to do any more work

   781     if (!matchCount)

   782         return this;

   783     

   784     UChar* data;

   785     PassRefPtr<StringImpl> newImpl =

   786         createUninitialized(m_length + matchCount * (repStrLength - patternLength), data);

   787     

   788     // Construct the new data

   789     int srcSegmentEnd;

   790     int srcSegmentLength;

   791     srcSegmentStart = 0;

   792     int dstOffset = 0;

   793     

   794     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) >= 0) {

   795         srcSegmentLength = srcSegmentEnd - srcSegmentStart;

   796         memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));

   797         dstOffset += srcSegmentLength;

   798         memcpy(data + dstOffset, replacement->m_data, repStrLength * sizeof(UChar));

   799         dstOffset += repStrLength;

   800         srcSegmentStart = srcSegmentEnd + patternLength;

   801     }

   802 

   803     srcSegmentLength = m_length - srcSegmentStart;

   804     memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));

   805 

   806     ASSERT(dstOffset + srcSegmentLength == static_cast<int>(newImpl->length()));

   807 

   808     return newImpl;

   809 }

   810 

   811 bool equal(const StringImpl* a, const StringImpl* b)

   812 {

   813     return StringHash::equal(a, b);

   814 }

   815 

   816 bool equal(const StringImpl* a, const char* b)

   817 {

   818     if (!a)

   819         return !b;

   820     if (!b)

   821         return !a;

   822 

   823     unsigned length = a->length();

   824     const UChar* as = a->characters();

   825     for (unsigned i = 0; i != length; ++i) {

   826         unsigned char bc = b[i];

   827         if (!bc)

   828             return false;

   829         if (as[i] != bc)

   830             return false;

   831     }

   832 

   833     return !b[length];

   834 }

   835 

   836 bool equalIgnoringCase(StringImpl* a, StringImpl* b)

   837 {

   838     return CaseFoldingHash::equal(a, b);

   839 }

   840 

   841 bool equalIgnoringCase(StringImpl* a, const char* b)

   842 {

   843     if (!a)

   844         return !b;

   845     if (!b)

   846         return !a;

   847 

   848     unsigned length = a->length();

   849     const UChar* as = a->characters();

   850 

   851     // Do a faster loop for the case where all the characters are ASCII.

   852     UChar ored = 0;

   853     bool equal = true;

   854     for (unsigned i = 0; i != length; ++i) {

   855         char bc = b[i];

   856         if (!bc)

   857             return false;

   858         UChar ac = as[i];

   859         ored |= ac;

   860         equal = equal && (toASCIILower(ac) == toASCIILower(bc));

   861     }

   862 

   863     // Do a slower implementation for cases that include non-ASCII characters.

   864     if (ored & ~0x7F) {

   865         equal = true;

   866         for (unsigned i = 0; i != length; ++i) {

   867             unsigned char bc = b[i];

   868             equal = equal && (foldCase(as[i]) == foldCase(bc));

   869         }

   870     }

   871 

   872     return equal && !b[length];

   873 }

   874 

   875 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)

   876 {

   877     if (StringHash::equal(a, b))

   878         return true;

   879     if (!a && b && !b->length())

   880         return true;

   881     if (!b && a && !a->length())

   882         return true;

   883 

   884     return false;

   885 }

   886 

   887 Vector<char> StringImpl::ascii()

   888 {

   889     Vector<char> buffer(m_length + 1);

   890     for (unsigned i = 0; i != m_length; ++i) {

   891         UChar c = m_data[i];

   892         if ((c >= 0x20 && c < 0x7F) || c == 0x00)

   893             buffer[i] = static_cast<char>(c);

   894         else

   895             buffer[i] = '?';

   896     }

   897     buffer[m_length] = '\0';

   898     return buffer;

   899 }

   900 

   901 WTF::Unicode::Direction StringImpl::defaultWritingDirection()

   902 {

   903     for (unsigned i = 0; i < m_length; ++i) {

   904         WTF::Unicode::Direction charDirection = WTF::Unicode::direction(m_data[i]);

   905         if (charDirection == WTF::Unicode::LeftToRight)

   906             return WTF::Unicode::LeftToRight;

   907         if (charDirection == WTF::Unicode::RightToLeft || charDirection == WTF::Unicode::RightToLeftArabic)

   908             return WTF::Unicode::RightToLeft;

   909     }

   910     return WTF::Unicode::LeftToRight;

   911 }

   912 

   913 // This is a hot function because it's used when parsing HTML.

   914 PassRefPtr<StringImpl> StringImpl::createStrippingNullCharactersSlowCase(const UChar* characters, unsigned length)

   915 {

   916     StringBuffer strippedCopy(length);

   917     unsigned strippedLength = 0;

   918     for (unsigned i = 0; i < length; i++) {

   919         if (int c = characters[i])

   920             strippedCopy[strippedLength++] = c;

   921     }

   922     ASSERT(strippedLength < length);  // Only take the slow case when stripping.

   923     strippedCopy.shrink(strippedLength);

   924     return adopt(strippedCopy);

   925 }

   926 

   927 PassRefPtr<StringImpl> StringImpl::adopt(StringBuffer& buffer)

   928 {

   929     unsigned length = buffer.length();

   930     if (length == 0)

   931         return empty();

   932     return adoptRef(new StringImpl(buffer.release(), length));

   933 }

   934 

   935 PassRefPtr<StringImpl> StringImpl::createWithTerminatingNullCharacter(const StringImpl& string)

   936 {

   937     // Use createUninitialized instead of 'new StringImpl' so that the string and its buffer

   938     // get allocated in a single malloc block.

   939     UChar* data;

   940     int length = string.m_length;

   941     RefPtr<StringImpl> terminatedString = createUninitialized(length + 1, data);

   942     memcpy(data, string.m_data, length * sizeof(UChar));

   943     data[length] = 0;

   944     terminatedString->m_length--;

   945     terminatedString->m_hash = string.m_hash;

   946     terminatedString->m_refCountAndFlags |= s_refCountFlagHasTerminatingNullCharacter;

   947     return terminatedString.release();

   948 }

   949 

   950 PassRefPtr<StringImpl> StringImpl::threadsafeCopy() const

   951 {

   952     return create(m_data, m_length);

   953 }

   954 

   955 PassRefPtr<StringImpl> StringImpl::crossThreadString()

   956 {

   957     if (SharedUChar* sharedBuffer = this->sharedBuffer())

   958         return adoptRef(new StringImpl(m_data, m_length, sharedBuffer->crossThreadCopy()));

   959 

   960     // If no shared buffer is available, create a copy.

   961     return threadsafeCopy();

   962 }

   963 

   964 } // namespace WebCore