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 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 using namespace std;
  37
  38 namespace WebCore {
  39
  40 static const unsigned minLengthToShare = 20;
  41
  42 StringImpl::~StringImpl()
  43 {
  44     ASSERT(!isStatic());
  45
  46     if (isAtomic())
  47         AtomicString::remove(this);
  48 #if USE(JSC)
  49     if (isIdentifier())
  50         wtfThreadData().currentIdentifierTable()->remove(this);
  51 #endif
  52
  53     BufferOwnership ownership = bufferOwnership();
  54     if (ownership != BufferInternal) {
  55         if (ownership == BufferOwned) {
  56             ASSERT(!m_sharedBuffer);
  57             ASSERT(m_data);
  58             fastFree(const_cast<UChar*>(m_data));
  59         } else if (ownership == BufferSubstring) {
  60             ASSERT(m_substringBuffer);
  61             m_substringBuffer->deref();
  62         } else {
  63             ASSERT(ownership == BufferShared);
  64             ASSERT(m_sharedBuffer);
  65             m_sharedBuffer->deref();
  66         }
  67     }
  68 }
  69
  70 PassRefPtr<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data)
  71 {
  72     if (!length) {
  73         data = 0;
  74         return empty();
  75     }
  76
  77     // Allocate a single buffer large enough to contain the StringImpl
  78     // struct as well as the data which it contains. This removes one
  79     // heap allocation from this call.
  80     if (length > ((std::numeric_limits<size_t>::max() - sizeof(StringImpl)) / sizeof(UChar)))
  81         CRASH();
  82     size_t size = sizeof(StringImpl) + length * sizeof(UChar);
  83     StringImpl* string = static_cast<StringImpl*>(fastMalloc(size));
  84
  85     data = reinterpret_cast<UChar*>(string + 1);
  86     return adoptRef(new (string) StringImpl(length));
  87 }
  88
  89 PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length)
  90 {
  91     if (!characters || !length)
  92         return empty();
  93
  94     UChar* data;
  95     PassRefPtr<StringImpl> string = createUninitialized(length, data);
  96     memcpy(data, characters, length * sizeof(UChar));
  97     return string;
  98 }
  99
 100 PassRefPtr<StringImpl> StringImpl::create(const char* characters, unsigned length)
 101 {
 102     if (!characters || !length)
 103         return empty();
 104
 105     UChar* data;
 106     PassRefPtr<StringImpl> string = createUninitialized(length, data);
 107     for (unsigned i = 0; i != length; ++i) {
 108         unsigned char c = characters[i];
 109         data[i] = c;
 110     }
 111     return string;
 112 }
 113
 114 PassRefPtr<StringImpl> StringImpl::create(const char* string)
 115 {
 116     if (!string)
 117         return empty();
 118     return create(string, strlen(string));
 119 }
 120
 121 PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)
 122 {
 123     ASSERT(characters);
 124     ASSERT(minLengthToShare && length >= minLengthToShare);
 125     return adoptRef(new StringImpl(characters, length, sharedBuffer));
 126 }
 127
 128 SharedUChar* StringImpl::sharedBuffer()
 129 {
 130     if (m_length < minLengthToShare)
 131         return 0;
 132     // All static strings are smaller that the minimim length to share.
 133     ASSERT(!isStatic());
 134
 135     BufferOwnership ownership = bufferOwnership();
 136
 137     if (ownership == BufferInternal)
 138         return 0;
 139     if (ownership == BufferSubstring)
 140         return m_substringBuffer->sharedBuffer();
 141     if (ownership == BufferOwned) {
 142         ASSERT(!m_sharedBuffer);
 143         m_sharedBuffer = SharedUChar::create(new SharableUChar(m_data)).releaseRef();
 144         m_refCountAndFlags = (m_refCountAndFlags & ~s_refCountMaskBufferOwnership) | BufferShared;
 145     }
 146
 147     ASSERT(bufferOwnership() == BufferShared);
 148     ASSERT(m_sharedBuffer);
 149     return m_sharedBuffer;
 150 }
 151
 152 bool StringImpl::containsOnlyWhitespace()
 153 {
 154     // FIXME: The definition of whitespace here includes a number of characters
 155     // that are not whitespace from the point of view of RenderText; I wonder if
 156     // that's a problem in practice.
 157     for (unsigned i = 0; i < m_length; i++)
 158         if (!isASCIISpace(m_data[i]))
 159             return false;
 160     return true;
 161 }
 162
 163 PassRefPtr<StringImpl> StringImpl::substring(unsigned start, unsigned length)
 164 {
 165     if (start >= m_length)
 166         return empty();
 167     unsigned maxLength = m_length - start;
 168     if (length >= maxLength) {
 169         if (!start)
 170             return this;
 171         length = maxLength;
 172     }
 173     return create(m_data + start, length);
 174 }
 175
 176 UChar32 StringImpl::characterStartingAt(unsigned i)
 177 {
 178     if (U16_IS_SINGLE(m_data[i]))
 179         return m_data[i];
 180     if (i + 1 < m_length && U16_IS_LEAD(m_data[i]) && U16_IS_TRAIL(m_data[i + 1]))
 181         return U16_GET_SUPPLEMENTARY(m_data[i], m_data[i + 1]);
 182     return 0;
 183 }
 184
 185 PassRefPtr<StringImpl> StringImpl::lower()
 186 {
 187     // Note: This is a hot function in the Dromaeo benchmark, specifically the
 188     // no-op code path up through the first 'return' statement.
 189
 190     // First scan the string for uppercase and non-ASCII characters:
 191     UChar ored = 0;
 192     bool noUpper = true;
 193     const UChar *end = m_data + m_length;
 194     for (const UChar* chp = m_data; chp != end; chp++) {
 195         if (UNLIKELY(isASCIIUpper(*chp)))
 196             noUpper = false;
 197         ored |= *chp;
 198     }
 199
 200     // Nothing to do if the string is all ASCII with no uppercase.
 201     if (noUpper && !(ored & ~0x7F))
 202         return this;
 203
 204     int32_t length = m_length;
 205     UChar* data;
 206     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
 207
 208     if (!(ored & ~0x7F)) {
 209         // Do a faster loop for the case where all the characters are ASCII.
 210         for (int i = 0; i < length; i++) {
 211             UChar c = m_data[i];
 212             data[i] = toASCIILower(c);
 213         }
 214         return newImpl;
 215     }
 216
 217     // Do a slower implementation for cases that include non-ASCII characters.
 218     bool error;
 219     int32_t realLength = Unicode::toLower(data, length, m_data, m_length, &error);
 220     if (!error && realLength == length)
 221         return newImpl;
 222     newImpl = createUninitialized(realLength, data);
 223     Unicode::toLower(data, realLength, m_data, m_length, &error);
 224     if (error)
 225         return this;
 226     return newImpl;
 227 }
 228
 229 PassRefPtr<StringImpl> StringImpl::upper()
 230 {
 231     // This function could be optimized for no-op cases the way lower() is,
 232     // but in empirical testing, few actual calls to upper() are no-ops, so
 233     // it wouldn't be worth the extra time for pre-scanning.
 234     UChar* data;
 235     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
 236     int32_t length = m_length;
 237
 238     // Do a faster loop for the case where all the characters are ASCII.
 239     UChar ored = 0;
 240     for (int i = 0; i < length; i++) {
 241         UChar c = m_data[i];
 242         ored |= c;
 243         data[i] = toASCIIUpper(c);
 244     }
 245     if (!(ored & ~0x7F))
 246         return newImpl;
 247
 248     // Do a slower implementation for cases that include non-ASCII characters.
 249     bool error;
 250     int32_t realLength = Unicode::toUpper(data, length, m_data, m_length, &error);
 251     if (!error && realLength == length)
 252         return newImpl;
 253     newImpl = createUninitialized(realLength, data);
 254     Unicode::toUpper(data, realLength, m_data, m_length, &error);
 255     if (error)
 256         return this;
 257     return newImpl;
 258 }
 259
 260 PassRefPtr<StringImpl> StringImpl::secure(UChar aChar, bool last)
 261 {
 262     int length = m_length;
 263     Vector<UChar> data(length);
 264     if (length > 0) {
 265         for (int i = 0; i <  length - 1; ++i)
 266             data[i] = aChar;
 267         data[length - 1] = (last ? aChar : m_data[length - 1]);
 268     }
 269     return adopt(data);
 270 }
 271
 272 PassRefPtr<StringImpl> StringImpl::foldCase()
 273 {
 274     UChar* data;
 275     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
 276     int32_t length = m_length;
 277
 278     // Do a faster loop for the case where all the characters are ASCII.
 279     UChar ored = 0;
 280     for (int i = 0; i < length; i++) {
 281         UChar c = m_data[i];
 282         ored |= c;
 283         data[i] = toASCIILower(c);
 284     }
 285     if (!(ored & ~0x7F))
 286         return newImpl;
 287
 288     // Do a slower implementation for cases that include non-ASCII characters.
 289     bool error;
 290     int32_t realLength = Unicode::foldCase(data, length, m_data, m_length, &error);
 291     if (!error && realLength == length)
 292         return newImpl;
 293     newImpl = createUninitialized(realLength, data);
 294     Unicode::foldCase(data, realLength, m_data, m_length, &error);
 295     if (error)
 296         return this;
 297     return newImpl;
 298 }
 299
 300 PassRefPtr<StringImpl> StringImpl::stripWhiteSpace()
 301 {
 302     if (!m_length)
 303         return empty();
 304
 305     unsigned start = 0;
 306     unsigned end = m_length - 1;
 307
 308     // skip white space from start
 309     while (start <= end && isSpaceOrNewline(m_data[start]))
 310         start++;
 311
 312     // only white space
 313     if (start > end)
 314         return empty();
 315
 316     // skip white space from end
 317     while (end && isSpaceOrNewline(m_data[end]))
 318         end--;
 319
 320     if (!start && end == m_length - 1)
 321         return this;
 322     return create(m_data + start, end + 1 - start);
 323 }
 324
 325 PassRefPtr<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)
 326 {
 327     const UChar* from = m_data;
 328     const UChar* fromend = from + m_length;
 329
 330     // Assume the common case will not remove any characters
 331     while (from != fromend && !findMatch(*from))
 332         from++;
 333     if (from == fromend)
 334         return this;
 335
 336     StringBuffer data(m_length);
 337     UChar* to = data.characters();
 338     unsigned outc = from - m_data;
 339
 340     if (outc)
 341         memcpy(to, m_data, outc * sizeof(UChar));
 342
 343     while (true) {
 344         while (from != fromend && findMatch(*from))
 345             from++;
 346         while (from != fromend && !findMatch(*from))
 347             to[outc++] = *from++;
 348         if (from == fromend)
 349             break;
 350     }
 351
 352     data.shrink(outc);
 353
 354     return adopt(data);
 355 }
 356
 357 PassRefPtr<StringImpl> StringImpl::simplifyWhiteSpace()
 358 {
 359     StringBuffer data(m_length);
 360
 361     const UChar* from = m_data;
 362     const UChar* fromend = from + m_length;
 363     int outc = 0;
 364     bool changedToSpace = false;
 365
 366     UChar* to = data.characters();
 367
 368     while (true) {
 369         while (from != fromend && isSpaceOrNewline(*from)) {
 370             if (*from != ' ')
 371                 changedToSpace = true;
 372             from++;
 373         }
 374         while (from != fromend && !isSpaceOrNewline(*from))
 375             to[outc++] = *from++;
 376         if (from != fromend)
 377             to[outc++] = ' ';
 378         else
 379             break;
 380     }
 381
 382     if (outc > 0 && to[outc - 1] == ' ')
 383         outc--;
 384
 385     if (static_cast<unsigned>(outc) == m_length && !changedToSpace)
 386         return this;
 387
 388     data.shrink(outc);
 389
 390     return adopt(data);
 391 }
 392
 393 int StringImpl::toIntStrict(bool* ok, int base)
 394 {
 395     return charactersToIntStrict(m_data, m_length, ok, base);
 396 }
 397
 398 unsigned StringImpl::toUIntStrict(bool* ok, int base)
 399 {
 400     return charactersToUIntStrict(m_data, m_length, ok, base);
 401 }
 402
 403 int64_t StringImpl::toInt64Strict(bool* ok, int base)
 404 {
 405     return charactersToInt64Strict(m_data, m_length, ok, base);
 406 }
 407
 408 uint64_t StringImpl::toUInt64Strict(bool* ok, int base)
 409 {
 410     return charactersToUInt64Strict(m_data, m_length, ok, base);
 411 }
 412
 413 intptr_t StringImpl::toIntPtrStrict(bool* ok, int base)
 414 {
 415     return charactersToIntPtrStrict(m_data, m_length, ok, base);
 416 }
 417
 418 int StringImpl::toInt(bool* ok)
 419 {
 420     return charactersToInt(m_data, m_length, ok);
 421 }
 422
 423 unsigned StringImpl::toUInt(bool* ok)
 424 {
 425     return charactersToUInt(m_data, m_length, ok);
 426 }
 427
 428 int64_t StringImpl::toInt64(bool* ok)
 429 {
 430     return charactersToInt64(m_data, m_length, ok);
 431 }
 432
 433 uint64_t StringImpl::toUInt64(bool* ok)
 434 {
 435     return charactersToUInt64(m_data, m_length, ok);
 436 }
 437
 438 intptr_t StringImpl::toIntPtr(bool* ok)
 439 {
 440     return charactersToIntPtr(m_data, m_length, ok);
 441 }
 442
 443 double StringImpl::toDouble(bool* ok)
 444 {
 445     return charactersToDouble(m_data, m_length, ok);
 446 }
 447
 448 float StringImpl::toFloat(bool* ok)
 449 {
 450     return charactersToFloat(m_data, m_length, ok);
 451 }
 452
 453 static bool equal(const UChar* a, const char* b, int length)
 454 {
 455     ASSERT(length >= 0);
 456     while (length--) {
 457         unsigned char bc = *b++;
 458         if (*a++ != bc)
 459             return false;
 460     }
 461     return true;
 462 }
 463
 464 bool equalIgnoringCase(const UChar* a, const char* b, unsigned length)
 465 {
 466     while (length--) {
 467         unsigned char bc = *b++;
 468         if (foldCase(*a++) != foldCase(bc))
 469             return false;
 470     }
 471     return true;
 472 }
 473
 474 static inline bool equalIgnoringCase(const UChar* a, const UChar* b, int length)
 475 {
 476     ASSERT(length >= 0);
 477     return umemcasecmp(a, b, length) == 0;
 478 }
 479
 480 int StringImpl::find(const char* chs, int index, bool caseSensitive)
 481 {
 482     if (!chs || index < 0)
 483         return -1;
 484
 485     int chsLength = strlen(chs);
 486     int n = m_length - index;
 487     if (n < 0)
 488         return -1;
 489     n -= chsLength - 1;
 490     if (n <= 0)
 491         return -1;
 492
 493     const char* chsPlusOne = chs + 1;
 494     int chsLengthMinusOne = chsLength - 1;
 495
 496     const UChar* ptr = m_data + index - 1;
 497     if (caseSensitive) {
 498         UChar c = *chs;
 499         do {
 500             if (*++ptr == c && equal(ptr + 1, chsPlusOne, chsLengthMinusOne))
 501                 return m_length - chsLength - n + 1;
 502         } while (--n);
 503     } else {
 504         UChar lc = Unicode::foldCase(*chs);
 505         do {
 506             if (Unicode::foldCase(*++ptr) == lc && equalIgnoringCase(ptr + 1, chsPlusOne, chsLengthMinusOne))
 507                 return m_length - chsLength - n + 1;
 508         } while (--n);
 509     }
 510
 511     return -1;
 512 }
 513
 514 int StringImpl::find(UChar c, int start)
 515 {
 516     return WebCore::find(m_data, m_length, c, start);
 517 }
 518
 519 int StringImpl::find(CharacterMatchFunctionPtr matchFunction, int start)
 520 {
 521     return WebCore::find(m_data, m_length, matchFunction, start);
 522 }
 523
 524 int StringImpl::find(StringImpl* str, int index, bool caseSensitive)
 525 {
 526     /*
 527       We use a simple trick for efficiency's sake. Instead of
 528       comparing strings, we compare the sum of str with that of
 529       a part of this string. Only if that matches, we call memcmp
 530       or ucstrnicmp.
 531     */
 532     ASSERT(str);
 533     if (index < 0)
 534         index += m_length;
 535     int lstr = str->m_length;
 536     int lthis = m_length - index;
 537     if ((unsigned)lthis > m_length)
 538         return -1;
 539     int delta = lthis - lstr;
 540     if (delta < 0)
 541         return -1;
 542
 543     const UChar* uthis = m_data + index;
 544     const UChar* ustr = str->m_data;
 545     unsigned hthis = 0;
 546     unsigned hstr = 0;
 547     if (caseSensitive) {
 548         for (int i = 0; i < lstr; i++) {
 549             hthis += uthis[i];
 550             hstr += ustr[i];
 551         }
 552         int i = 0;
 553         while (1) {
 554             if (hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(UChar)) == 0)
 555                 return index + i;
 556             if (i == delta)
 557                 return -1;
 558             hthis += uthis[i + lstr];
 559             hthis -= uthis[i];
 560             i++;
 561         }
 562     } else {
 563         for (int i = 0; i < lstr; i++ ) {
 564             hthis += toASCIILower(uthis[i]);
 565             hstr += toASCIILower(ustr[i]);
 566         }
 567         int i = 0;
 568         while (1) {
 569             if (hthis == hstr && equalIgnoringCase(uthis + i, ustr, lstr))
 570                 return index + i;
 571             if (i == delta)
 572                 return -1;
 573             hthis += toASCIILower(uthis[i + lstr]);
 574             hthis -= toASCIILower(uthis[i]);
 575             i++;
 576         }
 577     }
 578 }
 579
 580 int StringImpl::reverseFind(UChar c, int index)
 581 {
 582     return WebCore::reverseFind(m_data, m_length, c, index);
 583 }
 584
 585 int StringImpl::reverseFind(StringImpl* str, int index, bool caseSensitive)
 586 {
 587     /*
 588      See StringImpl::find() for explanations.
 589      */
 590     ASSERT(str);
 591     int lthis = m_length;
 592     if (index < 0)
 593         index += lthis;
 594
 595     int lstr = str->m_length;
 596     int delta = lthis - lstr;
 597     if ( index < 0 || index > lthis || delta < 0 )
 598         return -1;
 599     if ( index > delta )
 600         index = delta;
 601
 602     const UChar *uthis = m_data;
 603     const UChar *ustr = str->m_data;
 604     unsigned hthis = 0;
 605     unsigned hstr = 0;
 606     int i;
 607     if (caseSensitive) {
 608         for ( i = 0; i < lstr; i++ ) {
 609             hthis += uthis[index + i];
 610             hstr += ustr[i];
 611         }
 612         i = index;
 613         while (1) {
 614             if (hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(UChar)) == 0)
 615                 return i;
 616             if (i == 0)
 617                 return -1;
 618             i--;
 619             hthis -= uthis[i + lstr];
 620             hthis += uthis[i];
 621         }
 622     } else {
 623         for (i = 0; i < lstr; i++) {
 624             hthis += toASCIILower(uthis[index + i]);
 625             hstr += toASCIILower(ustr[i]);
 626         }
 627         i = index;
 628         while (1) {
 629             if (hthis == hstr && equalIgnoringCase(uthis + i, ustr, lstr) )
 630                 return i;
 631             if (i == 0)
 632                 return -1;
 633             i--;
 634             hthis -= toASCIILower(uthis[i + lstr]);
 635             hthis += toASCIILower(uthis[i]);
 636         }
 637     }
 638
 639     // Should never get here.
 640     return -1;
 641 }
 642
 643 bool StringImpl::endsWith(StringImpl* m_data, bool caseSensitive)
 644 {
 645     ASSERT(m_data);
 646     int start = m_length - m_data->m_length;
 647     if (start >= 0)
 648         return (find(m_data, start, caseSensitive) == start);
 649     return false;
 650 }
 651
 652 PassRefPtr<StringImpl> StringImpl::replace(UChar oldC, UChar newC)
 653 {
 654     if (oldC == newC)
 655         return this;
 656     unsigned i;
 657     for (i = 0; i != m_length; ++i)
 658         if (m_data[i] == oldC)
 659             break;
 660     if (i == m_length)
 661         return this;
 662
 663     UChar* data;
 664     PassRefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
 665
 666     for (i = 0; i != m_length; ++i) {
 667         UChar ch = m_data[i];
 668         if (ch == oldC)
 669             ch = newC;
 670         data[i] = ch;
 671     }
 672     return newImpl;
 673 }
 674
 675 PassRefPtr<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str)
 676 {
 677     position = min(position, length());
 678     lengthToReplace = min(lengthToReplace, length() - position);
 679     unsigned lengthToInsert = str ? str->length() : 0;
 680     if (!lengthToReplace && !lengthToInsert)
 681         return this;
 682     UChar* data;
 683
 684     if ((length() - lengthToReplace) >= (numeric_limits<unsigned>::max() - lengthToInsert))
 685         CRASH();
 686
 687     PassRefPtr<StringImpl> newImpl =
 688         createUninitialized(length() - lengthToReplace + lengthToInsert, data);
 689     memcpy(data, characters(), position * sizeof(UChar));
 690     if (str)
 691         memcpy(data + position, str->characters(), lengthToInsert * sizeof(UChar));
 692     memcpy(data + position + lengthToInsert, characters() + position + lengthToReplace,
 693         (length() - position - lengthToReplace) * sizeof(UChar));
 694     return newImpl;
 695 }
 696
 697 PassRefPtr<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
 698 {
 699     if (!replacement)
 700         return this;
 701
 702     int repStrLength = replacement->length();
 703     int srcSegmentStart = 0;
 704     unsigned matchCount = 0;
 705
 706     // Count the matches
 707     while ((srcSegmentStart = find(pattern, srcSegmentStart)) >= 0) {
 708         ++matchCount;
 709         ++srcSegmentStart;
 710     }
 711
 712     // If we have 0 matches, we don't have to do any more work
 713     if (!matchCount)
 714         return this;
 715
 716     if (repStrLength && matchCount > numeric_limits<unsigned>::max() / repStrLength)
 717         CRASH();
 718
 719     unsigned replaceSize = matchCount * repStrLength;
 720     unsigned newSize = m_length - matchCount;
 721     if (newSize >= (numeric_limits<unsigned>::max() - replaceSize))
 722         CRASH();
 723
 724     newSize += replaceSize;
 725
 726     UChar* data;
 727     PassRefPtr<StringImpl> newImpl = createUninitialized(newSize, data);
 728
 729     // Construct the new data
 730     int srcSegmentEnd;
 731     int srcSegmentLength;
 732     srcSegmentStart = 0;
 733     int dstOffset = 0;
 734
 735     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) >= 0) {
 736         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
 737         memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));
 738         dstOffset += srcSegmentLength;
 739         memcpy(data + dstOffset, replacement->m_data, repStrLength * sizeof(UChar));
 740         dstOffset += repStrLength;
 741         srcSegmentStart = srcSegmentEnd + 1;
 742     }
 743
 744     srcSegmentLength = m_length - srcSegmentStart;
 745     memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));
 746
 747     ASSERT(dstOffset + srcSegmentLength == static_cast<int>(newImpl->length()));
 748
 749     return newImpl;
 750 }
 751
 752 PassRefPtr<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
 753 {
 754     if (!pattern || !replacement)
 755         return this;
 756
 757     int patternLength = pattern->length();
 758     if (!patternLength)
 759         return this;
 760
 761     int repStrLength = replacement->length();
 762     int srcSegmentStart = 0;
 763     unsigned matchCount = 0;
 764
 765     // Count the matches
 766     while ((srcSegmentStart = find(pattern, srcSegmentStart)) >= 0) {
 767         ++matchCount;
 768         srcSegmentStart += patternLength;
 769     }
 770
 771     // If we have 0 matches, we don't have to do any more work
 772     if (!matchCount)
 773         return this;
 774
 775     unsigned newSize = m_length - matchCount * patternLength;
 776     if (repStrLength && matchCount > numeric_limits<unsigned>::max() / repStrLength)
 777         CRASH();
 778
 779     if (newSize > (numeric_limits<unsigned>::max() - matchCount * repStrLength))
 780         CRASH();
 781
 782     newSize += matchCount * repStrLength;
 783
 784     UChar* data;
 785     PassRefPtr<StringImpl> newImpl = createUninitialized(newSize, data);
 786
 787     // Construct the new data
 788     int srcSegmentEnd;
 789     int srcSegmentLength;
 790     srcSegmentStart = 0;
 791     int dstOffset = 0;
 792
 793     while ((srcSegmentEnd = find(pattern, srcSegmentStart)) >= 0) {
 794         srcSegmentLength = srcSegmentEnd - srcSegmentStart;
 795         memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));
 796         dstOffset += srcSegmentLength;
 797         memcpy(data + dstOffset, replacement->m_data, repStrLength * sizeof(UChar));
 798         dstOffset += repStrLength;
 799         srcSegmentStart = srcSegmentEnd + patternLength;
 800     }
 801
 802     srcSegmentLength = m_length - srcSegmentStart;
 803     memcpy(data + dstOffset, m_data + srcSegmentStart, srcSegmentLength * sizeof(UChar));
 804
 805     ASSERT(dstOffset + srcSegmentLength == static_cast<int>(newImpl->length()));
 806
 807     return newImpl;
 808 }
 809
 810 bool equal(const StringImpl* a, const StringImpl* b)
 811 {
 812     return StringHash::equal(a, b);
 813 }
 814
 815 bool equal(const StringImpl* a, const char* b)
 816 {
 817     if (!a)
 818         return !b;
 819     if (!b)
 820         return !a;
 821
 822     unsigned length = a->length();
 823     const UChar* as = a->characters();
 824     for (unsigned i = 0; i != length; ++i) {
 825         unsigned char bc = b[i];
 826         if (!bc)
 827             return false;
 828         if (as[i] != bc)
 829             return false;
 830     }
 831
 832     return !b[length];
 833 }
 834
 835 bool equalIgnoringCase(StringImpl* a, StringImpl* b)
 836 {
 837     return CaseFoldingHash::equal(a, b);
 838 }
 839
 840 bool equalIgnoringCase(StringImpl* a, const char* b)
 841 {
 842     if (!a)
 843         return !b;
 844     if (!b)
 845         return !a;
 846
 847     unsigned length = a->length();
 848     const UChar* as = a->characters();
 849
 850     // Do a faster loop for the case where all the characters are ASCII.
 851     UChar ored = 0;
 852     bool equal = true;
 853     for (unsigned i = 0; i != length; ++i) {
 854         char bc = b[i];
 855         if (!bc)
 856             return false;
 857         UChar ac = as[i];
 858         ored |= ac;
 859         equal = equal && (toASCIILower(ac) == toASCIILower(bc));
 860     }
 861
 862     // Do a slower implementation for cases that include non-ASCII characters.
 863     if (ored & ~0x7F) {
 864         equal = true;
 865         for (unsigned i = 0; i != length; ++i) {
 866             unsigned char bc = b[i];
 867             equal = equal && (foldCase(as[i]) == foldCase(bc));
 868         }
 869     }
 870
 871     return equal && !b[length];
 872 }
 873
 874 bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
 875 {
 876     if (StringHash::equal(a, b))
 877         return true;
 878     if (!a && b && !b->length())
 879         return true;
 880     if (!b && a && !a->length())
 881         return true;
 882
 883     return false;
 884 }
 885
 886 Vector<char> StringImpl::ascii()
 887 {
 888     Vector<char> buffer(m_length + 1);
 889     for (unsigned i = 0; i != m_length; ++i) {
 890         UChar c = m_data[i];
 891         if ((c >= 0x20 && c < 0x7F) || c == 0x00)
 892             buffer[i] = static_cast<char>(c);
 893         else
 894             buffer[i] = '?';
 895     }
 896     buffer[m_length] = '\0';
 897     return buffer;
 898 }
 899
 900 WTF::Unicode::Direction StringImpl::defaultWritingDirection()
 901 {
 902     for (unsigned i = 0; i < m_length; ++i) {
 903         WTF::Unicode::Direction charDirection = WTF::Unicode::direction(m_data[i]);
 904         if (charDirection == WTF::Unicode::LeftToRight)
 905             return WTF::Unicode::LeftToRight;
 906         if (charDirection == WTF::Unicode::RightToLeft || charDirection == WTF::Unicode::RightToLeftArabic)
 907             return WTF::Unicode::RightToLeft;
 908     }
 909     return WTF::Unicode::LeftToRight;
 910 }
 911
 912 // This is a hot function because it's used when parsing HTML.
 913 PassRefPtr<StringImpl> StringImpl::createStrippingNullCharactersSlowCase(const UChar* characters, unsigned length)
 914 {
 915     StringBuffer strippedCopy(length);
 916     unsigned strippedLength = 0;
 917     for (unsigned i = 0; i < length; i++) {
 918         if (int c = characters[i])
 919             strippedCopy[strippedLength++] = c;
 920     }
 921     ASSERT(strippedLength < length);  // Only take the slow case when stripping.
 922     strippedCopy.shrink(strippedLength);
 923     return adopt(strippedCopy);
 924 }
 925
 926 PassRefPtr<StringImpl> StringImpl::adopt(StringBuffer& buffer)
 927 {
 928     unsigned length = buffer.length();
 929     if (length == 0)
 930         return empty();
 931     return adoptRef(new StringImpl(buffer.release(), length));
 932 }
 933
 934 int StringImpl::wordCount(int maxWordsToCount)
 935 {
 936     unsigned wordCount = 0;
 937     unsigned i;
 938     bool atWord = false;
 939     for (i = 0; i < m_length; i++) {
 940         if (u_isspace(m_data[i])) {
 941             atWord = false;
 942         } else if (!atWord) {
 943             wordCount++;
 944             if (wordCount >= (unsigned)maxWordsToCount)
 945                 return wordCount;
 946             atWord = true;
 947         }
 948     }
 949     return wordCount;
 950 }
 951
 952 PassRefPtr<StringImpl> StringImpl::createWithTerminatingNullCharacter(const StringImpl& string)
 953 {
 954     // Use createUninitialized instead of 'new StringImpl' so that the string and its buffer
 955     // get allocated in a single malloc block.
 956     UChar* data;
 957     int length = string.m_length;
 958     RefPtr<StringImpl> terminatedString = createUninitialized(length + 1, data);
 959     memcpy(data, string.m_data, length * sizeof(UChar));
 960     data[length] = 0;
 961     terminatedString->m_length--;
 962     terminatedString->m_hash = string.m_hash;
 963     terminatedString->m_refCountAndFlags |= s_refCountFlagHasTerminatingNullCharacter;
 964     return terminatedString.release();
 965 }
 966
 967 PassRefPtr<StringImpl> StringImpl::threadsafeCopy() const
 968 {
 969     return create(m_data, m_length);
 970 }
 971
 972 PassRefPtr<StringImpl> StringImpl::crossThreadString()
 973 {
 974     if (SharedUChar* sharedBuffer = this->sharedBuffer())
 975         return adoptRef(new StringImpl(m_data, m_length, sharedBuffer->crossThreadCopy()));
 976
 977     // If no shared buffer is available, create a copy.
 978     return threadsafeCopy();
 979 }
 980
 981 } // namespace WebCore