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