diff options
Diffstat (limited to 'Source/WTF/wtf/text/StringImpl.cpp')
| -rw-r--r-- | Source/WTF/wtf/text/StringImpl.cpp | 942 |
1 files changed, 473 insertions, 469 deletions
diff --git a/Source/WTF/wtf/text/StringImpl.cpp b/Source/WTF/wtf/text/StringImpl.cpp index 34794258c..ee66daf25 100644 --- a/Source/WTF/wtf/text/StringImpl.cpp +++ b/Source/WTF/wtf/text/StringImpl.cpp @@ -2,7 +2,7 @@ * Copyright (C) 1999 Lars Knoll (knoll@kde.org) * (C) 1999 Antti Koivisto (koivisto@kde.org) * (C) 2001 Dirk Mueller ( mueller@kde.org ) - * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2013 Apple Inc. All rights reserved. + * Copyright (C) 2003-2009, 2013-2016 Apple Inc. All rights reserved. * Copyright (C) 2006 Andrew Wellington (proton@wiretapped.net) * * This library is free software; you can redistribute it and/or @@ -30,12 +30,14 @@ #include "StringHash.h" #include <wtf/ProcessID.h> #include <wtf/StdLibExtras.h> -#include <wtf/WTFThreadData.h> #include <wtf/text/CString.h> +#include <wtf/text/StringView.h> +#include <wtf/text/SymbolImpl.h> +#include <wtf/text/SymbolRegistry.h> #include <wtf/unicode/CharacterNames.h> #include <wtf/unicode/UTF8.h> -#ifdef STRING_STATS +#if STRING_STATS #include <unistd.h> #include <wtf/DataLog.h> #endif @@ -44,27 +46,21 @@ namespace WTF { using namespace Unicode; -COMPILE_ASSERT(sizeof(StringImpl) == 2 * sizeof(int) + 3 * sizeof(void*), StringImpl_should_stay_small); +static_assert(sizeof(StringImpl) == 2 * sizeof(int) + 2 * sizeof(void*), "StringImpl should stay small"); -#ifdef STRING_STATS +#if STRING_STATS StringStats StringImpl::m_stringStats; -unsigned StringStats::s_stringRemovesTillPrintStats = StringStats::s_printStringStatsFrequency; +std::atomic<unsigned> StringStats::s_stringRemovesTillPrintStats(s_printStringStatsFrequency); -void StringStats::removeString(StringImpl* string) +void StringStats::removeString(StringImpl& string) { - unsigned length = string->length(); - bool isSubString = string->isSubString(); + unsigned length = string.length(); + bool isSubString = string.isSubString(); --m_totalNumberStrings; - if (string->has16BitShadow()) { - --m_numberUpconvertedStrings; - if (!isSubString) - m_totalUpconvertedData -= length; - } - - if (string->is8Bit()) { + if (string.is8Bit()) { --m_number8BitStrings; if (!isSubString) m_total8BitData -= length; @@ -87,46 +83,46 @@ void StringStats::printStats() unsigned long long totalNumberCharacters = m_total8BitData + m_total16BitData; double percent8Bit = m_totalNumberStrings ? ((double)m_number8BitStrings * 100) / (double)m_totalNumberStrings : 0.0; double average8bitLength = m_number8BitStrings ? (double)m_total8BitData / (double)m_number8BitStrings : 0.0; - dataLogF("%8u (%5.2f%%) 8 bit %12llu chars %12llu bytes avg length %6.1f\n", m_number8BitStrings, percent8Bit, m_total8BitData, m_total8BitData, average8bitLength); + dataLogF("%8u (%5.2f%%) 8 bit %12llu chars %12llu bytes avg length %6.1f\n", m_number8BitStrings.load(), percent8Bit, m_total8BitData.load(), m_total8BitData.load(), average8bitLength); double percent16Bit = m_totalNumberStrings ? ((double)m_number16BitStrings * 100) / (double)m_totalNumberStrings : 0.0; double average16bitLength = m_number16BitStrings ? (double)m_total16BitData / (double)m_number16BitStrings : 0.0; - dataLogF("%8u (%5.2f%%) 16 bit %12llu chars %12llu bytes avg length %6.1f\n", m_number16BitStrings, percent16Bit, m_total16BitData, m_total16BitData * 2, average16bitLength); - - double percentUpconverted = m_totalNumberStrings ? ((double)m_numberUpconvertedStrings * 100) / (double)m_number8BitStrings : 0.0; - double averageUpconvertedLength = m_numberUpconvertedStrings ? (double)m_totalUpconvertedData / (double)m_numberUpconvertedStrings : 0.0; - dataLogF("%8u (%5.2f%%) upconverted %12llu chars %12llu bytes avg length %6.1f\n", m_numberUpconvertedStrings, percentUpconverted, m_totalUpconvertedData, m_totalUpconvertedData * 2, averageUpconvertedLength); + dataLogF("%8u (%5.2f%%) 16 bit %12llu chars %12llu bytes avg length %6.1f\n", m_number16BitStrings.load(), percent16Bit, m_total16BitData.load(), m_total16BitData * 2, average16bitLength); double averageLength = m_totalNumberStrings ? (double)totalNumberCharacters / (double)m_totalNumberStrings : 0.0; - unsigned long long totalDataBytes = m_total8BitData + (m_total16BitData + m_totalUpconvertedData) * 2; - dataLogF("%8u Total %12llu chars %12llu bytes avg length %6.1f\n", m_totalNumberStrings, totalNumberCharacters, totalDataBytes, averageLength); - unsigned long long totalSavedBytes = m_total8BitData - m_totalUpconvertedData; + unsigned long long totalDataBytes = m_total8BitData + m_total16BitData * 2; + dataLogF("%8u Total %12llu chars %12llu bytes avg length %6.1f\n", m_totalNumberStrings.load(), totalNumberCharacters, totalDataBytes, averageLength); + unsigned long long totalSavedBytes = m_total8BitData; double percentSavings = totalSavedBytes ? ((double)totalSavedBytes * 100) / (double)(totalDataBytes + totalSavedBytes) : 0.0; dataLogF(" Total savings %12llu bytes (%5.2f%%)\n", totalSavedBytes, percentSavings); + + dataLogF("%8u StringImpl::ref calls\n", m_refCalls.load()); + dataLogF("%8u StringImpl::deref calls\n", m_derefCalls.load()); } #endif +StringImpl::StaticStringImpl StringImpl::s_atomicEmptyString("", StringImpl::StringAtomic); StringImpl::~StringImpl() { ASSERT(!isStatic()); - STRING_STATS_REMOVE_STRING(this); + StringView::invalidate(*this); - if (isAtomic()) - AtomicString::remove(this); - if (isIdentifier()) { - if (!wtfThreadData().currentIdentifierTable()->remove(this)) - CRASH(); - } + STRING_STATS_REMOVE_STRING(*this); - BufferOwnership ownership = bufferOwnership(); + if (isAtomic() && length() && !isSymbol()) + AtomicStringImpl::remove(static_cast<AtomicStringImpl*>(this)); - if (has16BitShadow()) { - ASSERT(m_copyData16); - fastFree(m_copyData16); + if (isSymbol()) { + auto& symbol = static_cast<SymbolImpl&>(*this); + auto* symbolRegistry = symbol.symbolRegistry(); + if (symbolRegistry) + symbolRegistry->remove(symbol); } + BufferOwnership ownership = bufferOwnership(); + if (ownership == BufferInternal) return; if (ownership == BufferOwned) { @@ -137,8 +133,8 @@ StringImpl::~StringImpl() } ASSERT(ownership == BufferSubstring); - ASSERT(m_substringBuffer); - m_substringBuffer->deref(); + ASSERT(substringBuffer()); + substringBuffer()->deref(); } void StringImpl::destroy(StringImpl* stringImpl) @@ -147,19 +143,19 @@ void StringImpl::destroy(StringImpl* stringImpl) fastFree(stringImpl); } -PassRef<StringImpl> StringImpl::createFromLiteral(const char* characters, unsigned length) +Ref<StringImpl> StringImpl::createFromLiteral(const char* characters, unsigned length) { ASSERT_WITH_MESSAGE(length, "Use StringImpl::empty() to create an empty string"); ASSERT(charactersAreAllASCII<LChar>(reinterpret_cast<const LChar*>(characters), length)); return adoptRef(*new StringImpl(reinterpret_cast<const LChar*>(characters), length, ConstructWithoutCopying)); } -PassRef<StringImpl> StringImpl::createFromLiteral(const char* characters) +Ref<StringImpl> StringImpl::createFromLiteral(const char* characters) { return createFromLiteral(characters, strlen(characters)); } -PassRef<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, unsigned length) +Ref<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, unsigned length) { if (!length) return *empty(); @@ -167,7 +163,7 @@ PassRef<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, un return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying)); } -PassRef<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, unsigned length) +Ref<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, unsigned length) { if (!length) return *empty(); @@ -176,7 +172,7 @@ PassRef<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, un } template <typename CharType> -inline PassRef<StringImpl> StringImpl::createUninitializedInternal(unsigned length, CharType*& data) +inline Ref<StringImpl> StringImpl::createUninitializedInternal(unsigned length, CharType*& data) { if (!length) { data = 0; @@ -186,7 +182,7 @@ inline PassRef<StringImpl> StringImpl::createUninitializedInternal(unsigned leng } template <typename CharType> -inline PassRef<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsigned length, CharType*& data) +inline Ref<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsigned length, CharType*& data) { ASSERT(length); @@ -195,26 +191,25 @@ inline PassRef<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsig // heap allocation from this call. if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharType))) CRASH(); - size_t size = sizeof(StringImpl) + length * sizeof(CharType); - StringImpl* string = static_cast<StringImpl*>(fastMalloc(size)); + StringImpl* string = static_cast<StringImpl*>(fastMalloc(allocationSize<CharType>(length))); - data = reinterpret_cast<CharType*>(string + 1); + data = string->tailPointer<CharType>(); return constructInternal<CharType>(string, length); } -PassRef<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data) +Ref<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data) { return createUninitializedInternal(length, data); } -PassRef<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data) +Ref<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data) { return createUninitializedInternal(length, data); } template <typename CharType> -inline PassRef<StringImpl> StringImpl::reallocateInternal(PassRefPtr<StringImpl> originalString, unsigned length, CharType*& data) -{ +inline Ref<StringImpl> StringImpl::reallocateInternal(Ref<StringImpl>&& originalString, unsigned length, CharType*& data) +{ ASSERT(originalString->hasOneRef()); ASSERT(originalString->bufferOwnership() == BufferInternal); @@ -226,28 +221,28 @@ inline PassRef<StringImpl> StringImpl::reallocateInternal(PassRefPtr<StringImpl> // Same as createUninitialized() except here we use fastRealloc. if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharType))) CRASH(); - size_t size = sizeof(StringImpl) + length * sizeof(CharType); + originalString->~StringImpl(); - StringImpl* string = static_cast<StringImpl*>(fastRealloc(originalString.leakRef(), size)); + auto* string = static_cast<StringImpl*>(fastRealloc(&originalString.leakRef(), allocationSize<CharType>(length))); - data = reinterpret_cast<CharType*>(string + 1); + data = string->tailPointer<CharType>(); return constructInternal<CharType>(string, length); } -PassRef<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, LChar*& data) +Ref<StringImpl> StringImpl::reallocate(Ref<StringImpl>&& originalString, unsigned length, LChar*& data) { ASSERT(originalString->is8Bit()); - return reallocateInternal(originalString, length, data); + return reallocateInternal(WTFMove(originalString), length, data); } -PassRef<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, UChar*& data) +Ref<StringImpl> StringImpl::reallocate(Ref<StringImpl>&& originalString, unsigned length, UChar*& data) { ASSERT(!originalString->is8Bit()); - return reallocateInternal(originalString, length, data); + return reallocateInternal(WTFMove(originalString), length, data); } template <typename CharType> -inline PassRef<StringImpl> StringImpl::createInternal(const CharType* characters, unsigned length) +inline Ref<StringImpl> StringImpl::createInternal(const CharType* characters, unsigned length) { if (!characters || !length) return *empty(); @@ -258,23 +253,23 @@ inline PassRef<StringImpl> StringImpl::createInternal(const CharType* characters return string; } -PassRef<StringImpl> StringImpl::create(const UChar* characters, unsigned length) +Ref<StringImpl> StringImpl::create(const UChar* characters, unsigned length) { return createInternal(characters, length); } -PassRef<StringImpl> StringImpl::create(const LChar* characters, unsigned length) +Ref<StringImpl> StringImpl::create(const LChar* characters, unsigned length) { return createInternal(characters, length); } -PassRef<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length) +Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length) { if (!characters || !length) return *empty(); LChar* data; - RefPtr<StringImpl> string = createUninitializedInternalNonEmpty(length, data); + auto string = createUninitializedInternalNonEmpty(length, data); for (size_t i = 0; i < length; ++i) { if (characters[i] & 0xff00) @@ -282,15 +277,15 @@ PassRef<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, un data[i] = static_cast<LChar>(characters[i]); } - return string.releaseNonNull(); + return string; } -PassRef<StringImpl> StringImpl::create8BitIfPossible(const UChar* string) +Ref<StringImpl> StringImpl::create8BitIfPossible(const UChar* string) { return StringImpl::create8BitIfPossible(string, lengthOfNullTerminatedString(string)); } -PassRef<StringImpl> StringImpl::create(const LChar* string) +Ref<StringImpl> StringImpl::create(const LChar* string) { if (!string) return *empty(); @@ -300,41 +295,6 @@ PassRef<StringImpl> StringImpl::create(const LChar* string) return create(string, length); } -const UChar* StringImpl::getData16SlowCase() const -{ - if (has16BitShadow()) - return m_copyData16; - - if (bufferOwnership() == BufferSubstring) { - // If this is a substring, return a pointer into the parent string. - // TODO: Consider severing this string from the parent string - unsigned offset = m_data8 - m_substringBuffer->characters8(); - return m_substringBuffer->deprecatedCharacters() + offset; - } - - STRING_STATS_ADD_UPCONVERTED_STRING(m_length); - - unsigned len = length(); - - m_copyData16 = static_cast<UChar*>(fastMalloc(len * sizeof(UChar))); - - m_hashAndFlags |= s_hashFlagHas16BitShadow; - - upconvertCharacters(0, len); - - return m_copyData16; -} - -void StringImpl::upconvertCharacters(unsigned start, unsigned end) const -{ - ASSERT(is8Bit()); - ASSERT(has16BitShadow()); - - for (size_t i = start; i < end; ++i) - m_copyData16[i] = m_data8[i]; -} - - bool StringImpl::containsOnlyWhitespace() { // FIXME: The definition of whitespace here includes a number of characters @@ -358,7 +318,7 @@ bool StringImpl::containsOnlyWhitespace() return true; } -PassRef<StringImpl> StringImpl::substring(unsigned start, unsigned length) +Ref<StringImpl> StringImpl::substring(unsigned start, unsigned length) { if (start >= m_length) return *empty(); @@ -385,42 +345,23 @@ UChar32 StringImpl::characterStartingAt(unsigned i) return 0; } -PassRef<StringImpl> StringImpl::lower() +Ref<StringImpl> StringImpl::convertToLowercaseWithoutLocale() { - // Note: This is a hot function in the Dromaeo benchmark, specifically the - // no-op code path up through the first 'return' statement. + // Note: At one time this was a hot function in the Dromaeo benchmark, specifically the + // no-op code path that may return ourself if we find no upper case letters and no invalid + // ASCII letters. // First scan the string for uppercase and non-ASCII characters: if (is8Bit()) { - unsigned failingIndex; for (unsigned i = 0; i < m_length; ++i) { LChar character = m_data8[i]; - if (UNLIKELY((character & ~0x7F) || isASCIIUpper(character))) { - failingIndex = i; - goto SlowPath8bitLower; - } - } - return *this; - -SlowPath8bitLower: - LChar* data8; - auto newImpl = createUninitializedInternalNonEmpty(m_length, data8); - - for (unsigned i = 0; i < failingIndex; ++i) - data8[i] = m_data8[i]; - - for (unsigned i = failingIndex; i < m_length; ++i) { - LChar character = m_data8[i]; - if (!(character & ~0x7F)) - data8[i] = toASCIILower(character); - else { - ASSERT(u_tolower(character) <= 0xFF); - data8[i] = static_cast<LChar>(u_tolower(character)); - } + if (UNLIKELY((character & ~0x7F) || isASCIIUpper(character))) + return convertToLowercaseWithoutLocaleStartingAtFailingIndex8Bit(i); } - return newImpl; + return *this; } + bool noUpper = true; unsigned ored = 0; @@ -451,26 +392,51 @@ SlowPath8bitLower: // Do a slower implementation for cases that include non-ASCII characters. UChar* data16; - RefPtr<StringImpl> newImpl = createUninitializedInternalNonEmpty(m_length, data16); + auto newImpl = createUninitializedInternalNonEmpty(m_length, data16); UErrorCode status = U_ZERO_ERROR; int32_t realLength = u_strToLower(data16, length, m_data16, m_length, "", &status); if (U_SUCCESS(status) && realLength == length) - return newImpl.releaseNonNull(); + return newImpl; newImpl = createUninitialized(realLength, data16); status = U_ZERO_ERROR; u_strToLower(data16, realLength, m_data16, m_length, "", &status); if (U_FAILURE(status)) return *this; - return newImpl.releaseNonNull(); + return newImpl; +} + +Ref<StringImpl> StringImpl::convertToLowercaseWithoutLocaleStartingAtFailingIndex8Bit(unsigned failingIndex) +{ + ASSERT(is8Bit()); + LChar* data8; + auto newImpl = createUninitializedInternalNonEmpty(m_length, data8); + + for (unsigned i = 0; i < failingIndex; ++i) { + ASSERT(!(m_data8[i] & ~0x7F) && !isASCIIUpper(m_data8[i])); + data8[i] = m_data8[i]; + } + + for (unsigned i = failingIndex; i < m_length; ++i) { + LChar character = m_data8[i]; + if (!(character & ~0x7F)) + data8[i] = toASCIILower(character); + else { + ASSERT(u_tolower(character) <= 0xFF); + data8[i] = static_cast<LChar>(u_tolower(character)); + } + } + + return newImpl; } -PassRef<StringImpl> StringImpl::upper() +Ref<StringImpl> StringImpl::convertToUppercaseWithoutLocale() { - // This function could be optimized for no-op cases the way lower() is, - // but in empirical testing, few actual calls to upper() are no-ops, so - // it wouldn't be worth the extra time for pre-scanning. + // This function could be optimized for no-op cases the way + // convertToLowercaseWithoutLocale() is, but in empirical testing, + // few actual calls to upper() are no-ops, so it wouldn't be worth + // the extra time for pre-scanning. if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max())) CRASH(); @@ -478,30 +444,23 @@ PassRef<StringImpl> StringImpl::upper() if (is8Bit()) { LChar* data8; - RefPtr<StringImpl> newImpl = createUninitialized(m_length, data8); + auto newImpl = createUninitialized(m_length, data8); // Do a faster loop for the case where all the characters are ASCII. unsigned ored = 0; for (int i = 0; i < length; ++i) { LChar c = m_data8[i]; ored |= c; -#if CPU(X86) && defined(_MSC_VER) && _MSC_VER >=1700 - // Workaround for an MSVC 2012 x86 optimizer bug. Remove once the bug is fixed. - // See https://connect.microsoft.com/VisualStudio/feedback/details/780362/optimization-bug-of-range-comparison - // for more details. - data8[i] = c >= 'a' && c <= 'z' ? c & ~0x20 : c; -#else data8[i] = toASCIIUpper(c); -#endif } if (!(ored & ~0x7F)) - return newImpl.releaseNonNull(); + return newImpl; // Do a slower implementation for cases that include non-ASCII Latin-1 characters. int numberSharpSCharacters = 0; // There are two special cases. - // 1. latin-1 characters when converted to upper case are 16 bit characters. + // 1. Some Latin-1 characters when converted to upper case are 16 bit characters. // 2. Lower case sharp-S converts to "SS" (two characters) for (int32_t i = 0; i < length; ++i) { LChar c = m_data8[i]; @@ -509,7 +468,7 @@ PassRef<StringImpl> StringImpl::upper() ++numberSharpSCharacters; ASSERT(u_toupper(c) <= 0xFFFF); UChar upper = u_toupper(c); - if (UNLIKELY(upper > 0xff)) { + if (UNLIKELY(upper > 0xFF)) { // Since this upper-cased character does not fit in an 8-bit string, we need to take the 16-bit path. goto upconvert; } @@ -517,7 +476,7 @@ PassRef<StringImpl> StringImpl::upper() } if (!numberSharpSCharacters) - return newImpl.releaseNonNull(); + return newImpl; // We have numberSSCharacters sharp-s characters, but none of the other special characters. newImpl = createUninitialized(m_length + numberSharpSCharacters, data8); @@ -535,14 +494,15 @@ PassRef<StringImpl> StringImpl::upper() } } - return newImpl.releaseNonNull(); + return newImpl; } upconvert: - const UChar* source16 = deprecatedCharacters(); + auto upconvertedCharacters = StringView(*this).upconvertedCharacters(); + const UChar* source16 = upconvertedCharacters; UChar* data16; - RefPtr<StringImpl> newImpl = createUninitialized(m_length, data16); + auto newImpl = createUninitialized(m_length, data16); // Do a faster loop for the case where all the characters are ASCII. unsigned ored = 0; @@ -552,19 +512,19 @@ upconvert: data16[i] = toASCIIUpper(c); } if (!(ored & ~0x7F)) - return newImpl.releaseNonNull(); + return newImpl; // Do a slower implementation for cases that include non-ASCII characters. UErrorCode status = U_ZERO_ERROR; int32_t realLength = u_strToUpper(data16, length, source16, m_length, "", &status); if (U_SUCCESS(status) && realLength == length) - return newImpl.releaseNonNull(); + return newImpl; newImpl = createUninitialized(realLength, data16); status = U_ZERO_ERROR; u_strToUpper(data16, realLength, source16, m_length, "", &status); if (U_FAILURE(status)) return *this; - return newImpl.releaseNonNull(); + return newImpl; } static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier) @@ -577,14 +537,14 @@ static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier) && (localeIdentifier.length() == 2 || localeIdentifier[2] == '-'); } -PassRef<StringImpl> StringImpl::lower(const AtomicString& localeIdentifier) +Ref<StringImpl> StringImpl::convertToLowercaseWithLocale(const AtomicString& localeIdentifier) { // Use the more-optimized code path most of the time. // Assuming here that the only locale-specific lowercasing is the Turkish casing rules. // FIXME: Could possibly optimize further by looking for the specific sequences // that have locale-specific lowercasing. There are only three of them. if (!needsTurkishCasingRules(localeIdentifier)) - return lower(); + return convertToLowercaseWithoutLocale(); // FIXME: Could share more code with the main StringImpl::lower by factoring out // this last part into a shared function that takes a locale string, since this is @@ -597,28 +557,29 @@ PassRef<StringImpl> StringImpl::lower(const AtomicString& localeIdentifier) // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than // allocating memory just to turn localeIdentifier into a C string, and we assume // there is no difference between the uppercasing for "tr" and "az" locales. - const UChar* source16 = deprecatedCharacters(); + auto upconvertedCharacters = StringView(*this).upconvertedCharacters(); + const UChar* source16 = upconvertedCharacters; UChar* data16; - RefPtr<StringImpl> newString = createUninitialized(length, data16); + auto newString = createUninitialized(length, data16); UErrorCode status = U_ZERO_ERROR; int realLength = u_strToLower(data16, length, source16, length, "tr", &status); if (U_SUCCESS(status) && realLength == length) - return newString.releaseNonNull(); + return newString; newString = createUninitialized(realLength, data16); status = U_ZERO_ERROR; u_strToLower(data16, realLength, source16, length, "tr", &status); if (U_FAILURE(status)) return *this; - return newString.releaseNonNull(); + return newString; } -PassRef<StringImpl> StringImpl::upper(const AtomicString& localeIdentifier) +Ref<StringImpl> StringImpl::convertToUppercaseWithLocale(const AtomicString& localeIdentifier) { // Use the more-optimized code path most of the time. // Assuming here that the only locale-specific lowercasing is the Turkish casing rules, // and that the only affected character is lowercase "i". if (!needsTurkishCasingRules(localeIdentifier) || find('i') == notFound) - return upper(); + return convertToUppercaseWithoutLocale(); if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max())) CRASH(); @@ -627,95 +588,145 @@ PassRef<StringImpl> StringImpl::upper(const AtomicString& localeIdentifier) // Below, we pass in the hardcoded locale "tr". Passing that is more efficient than // allocating memory just to turn localeIdentifier into a C string, and we assume // there is no difference between the uppercasing for "tr" and "az" locales. - const UChar* source16 = deprecatedCharacters(); + auto upconvertedCharacters = StringView(*this).upconvertedCharacters(); + const UChar* source16 = upconvertedCharacters; UChar* data16; - RefPtr<StringImpl> newString = createUninitialized(length, data16); + auto newString = createUninitialized(length, data16); UErrorCode status = U_ZERO_ERROR; int realLength = u_strToUpper(data16, length, source16, length, "tr", &status); if (U_SUCCESS(status) && realLength == length) - return newString.releaseNonNull(); + return newString; newString = createUninitialized(realLength, data16); status = U_ZERO_ERROR; u_strToUpper(data16, realLength, source16, length, "tr", &status); if (U_FAILURE(status)) return *this; - return newString.releaseNonNull(); -} - -PassRef<StringImpl> StringImpl::fill(UChar character) -{ - if (!(character & ~0x7F)) { - LChar* data; - auto newImpl = createUninitialized(m_length, data); - for (unsigned i = 0; i < m_length; ++i) - data[i] = character; - return newImpl; - } - UChar* data; - auto newImpl = createUninitialized(m_length, data); - for (unsigned i = 0; i < m_length; ++i) - data[i] = character; - return newImpl; + return newString; } -PassRef<StringImpl> StringImpl::foldCase() +Ref<StringImpl> StringImpl::foldCase() { - if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max())) - CRASH(); - int32_t length = m_length; - if (is8Bit()) { - // Do a faster loop for the case where all the characters are ASCII. - LChar* data; - auto newImpl = createUninitialized(m_length, data); - LChar ored = 0; - - for (int32_t i = 0; i < length; ++i) { - LChar c = m_data8[i]; - data[i] = toASCIILower(c); - ored |= c; + unsigned failingIndex; + for (unsigned i = 0; i < m_length; ++i) { + auto character = m_data8[i]; + if (UNLIKELY(!isASCII(character) || isASCIIUpper(character))) { + failingIndex = i; + goto SlowPath; + } } + // String was all ASCII and no uppercase, so just return as-is. + return *this; - if (!(ored & ~0x7F)) - return newImpl; - - // Do a slower implementation for cases that include non-ASCII Latin-1 characters. - // FIXME: Shouldn't this use u_foldCase instead of u_tolower? - for (int32_t i = 0; i < length; ++i) { - ASSERT(u_tolower(m_data8[i]) <= 0xFF); - data[i] = static_cast<LChar>(u_tolower(m_data8[i])); +SlowPath: + bool need16BitCharacters = false; + for (unsigned i = failingIndex; i < m_length; ++i) { + auto character = m_data8[i]; + if (character == 0xB5 || character == 0xDF) { + need16BitCharacters = true; + break; + } } - return newImpl; + if (!need16BitCharacters) { + LChar* data8; + auto folded = createUninitializedInternalNonEmpty(m_length, data8); + for (unsigned i = 0; i < failingIndex; ++i) + data8[i] = m_data8[i]; + for (unsigned i = failingIndex; i < m_length; ++i) { + auto character = m_data8[i]; + if (isASCII(character)) + data8[i] = toASCIILower(character); + else { + ASSERT(u_foldCase(character, U_FOLD_CASE_DEFAULT) <= 0xFF); + data8[i] = static_cast<LChar>(u_foldCase(character, U_FOLD_CASE_DEFAULT)); + } + } + return folded; + } + } else { + // FIXME: Unclear why we use goto in the 8-bit case, and a different approach in the 16-bit case. + bool noUpper = true; + unsigned ored = 0; + for (unsigned i = 0; i < m_length; ++i) { + UChar character = m_data16[i]; + if (UNLIKELY(isASCIIUpper(character))) + noUpper = false; + ored |= character; + } + if (!(ored & ~0x7F)) { + if (noUpper) { + // String was all ASCII and no uppercase, so just return as-is. + return *this; + } + UChar* data16; + auto folded = createUninitializedInternalNonEmpty(m_length, data16); + for (unsigned i = 0; i < m_length; ++i) + data16[i] = toASCIILower(m_data16[i]); + return folded; + } } - // Do a faster loop for the case where all the characters are ASCII. - UChar* data; - RefPtr<StringImpl> newImpl = createUninitialized(m_length, data); - UChar ored = 0; - for (int32_t i = 0; i < length; ++i) { - UChar c = m_data16[i]; - ored |= c; - data[i] = toASCIILower(c); - } - if (!(ored & ~0x7F)) - return newImpl.releaseNonNull(); + if (m_length > static_cast<unsigned>(std::numeric_limits<int32_t>::max())) + CRASH(); - // Do a slower implementation for cases that include non-ASCII characters. + auto upconvertedCharacters = StringView(*this).upconvertedCharacters(); + + UChar* data; + auto folded = createUninitializedInternalNonEmpty(m_length, data); + int32_t length = m_length; UErrorCode status = U_ZERO_ERROR; - int32_t realLength = u_strFoldCase(data, length, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status); + int32_t realLength = u_strFoldCase(data, length, upconvertedCharacters, length, U_FOLD_CASE_DEFAULT, &status); if (U_SUCCESS(status) && realLength == length) - return newImpl.releaseNonNull(); - newImpl = createUninitialized(realLength, data); + return folded; + ASSERT(realLength > length); + folded = createUninitializedInternalNonEmpty(realLength, data); status = U_ZERO_ERROR; - u_strFoldCase(data, realLength, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status); + u_strFoldCase(data, realLength, upconvertedCharacters, length, U_FOLD_CASE_DEFAULT, &status); if (U_FAILURE(status)) return *this; - return newImpl.releaseNonNull(); + return folded; +} + +template<StringImpl::CaseConvertType type, typename CharacterType> +ALWAYS_INLINE Ref<StringImpl> StringImpl::convertASCIICase(StringImpl& impl, const CharacterType* data, unsigned length) +{ + unsigned failingIndex; + for (unsigned i = 0; i < length; ++i) { + CharacterType character = data[i]; + if (type == CaseConvertType::Lower ? UNLIKELY(isASCIIUpper(character)) : LIKELY(isASCIILower(character))) { + failingIndex = i; + goto SlowPath; + } + } + return impl; + +SlowPath: + CharacterType* newData; + auto newImpl = createUninitializedInternalNonEmpty(length, newData); + for (unsigned i = 0; i < failingIndex; ++i) + newData[i] = data[i]; + for (unsigned i = failingIndex; i < length; ++i) + newData[i] = type == CaseConvertType::Lower ? toASCIILower(data[i]) : toASCIIUpper(data[i]); + return newImpl; +} + +Ref<StringImpl> StringImpl::convertToASCIILowercase() +{ + if (is8Bit()) + return convertASCIICase<CaseConvertType::Lower>(*this, m_data8, m_length); + return convertASCIICase<CaseConvertType::Lower>(*this, m_data16, m_length); +} + +Ref<StringImpl> StringImpl::convertToASCIIUppercase() +{ + if (is8Bit()) + return convertASCIICase<CaseConvertType::Upper>(*this, m_data8, m_length); + return convertASCIICase<CaseConvertType::Upper>(*this, m_data16, m_length); } template <class UCharPredicate> -inline PassRef<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate) +inline Ref<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate) { if (!m_length) return *this; @@ -763,18 +774,18 @@ public: } }; -PassRef<StringImpl> StringImpl::stripWhiteSpace() +Ref<StringImpl> StringImpl::stripWhiteSpace() { return stripMatchedCharacters(SpaceOrNewlinePredicate()); } -PassRef<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace) +Ref<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace) { return stripMatchedCharacters(UCharPredicate(isWhiteSpace)); } template <typename CharType> -ALWAYS_INLINE PassRef<StringImpl> StringImpl::removeCharacters(const CharType* characters, CharacterMatchFunctionPtr findMatch) +ALWAYS_INLINE Ref<StringImpl> StringImpl::removeCharacters(const CharType* characters, CharacterMatchFunctionPtr findMatch) { const CharType* from = characters; const CharType* fromend = from + m_length; @@ -803,10 +814,10 @@ ALWAYS_INLINE PassRef<StringImpl> StringImpl::removeCharacters(const CharType* c data.shrink(outc); - return adopt(data); + return adopt(WTFMove(data)); } -PassRef<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch) +Ref<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch) { if (is8Bit()) return removeCharacters(characters8(), findMatch); @@ -814,11 +825,11 @@ PassRef<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findM } template <typename CharType, class UCharPredicate> -inline PassRef<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate) +inline Ref<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate) { StringBuffer<CharType> data(m_length); - const CharType* from = getCharacters<CharType>(); + const CharType* from = characters<CharType>(); const CharType* fromend = from + m_length; int outc = 0; bool changedToSpace = false; @@ -847,17 +858,17 @@ inline PassRef<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPre data.shrink(outc); - return adopt(data); + return adopt(WTFMove(data)); } -PassRef<StringImpl> StringImpl::simplifyWhiteSpace() +Ref<StringImpl> StringImpl::simplifyWhiteSpace() { if (is8Bit()) return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate()); return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate()); } -PassRef<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace) +Ref<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace) { if (is8Bit()) return StringImpl::simplifyMatchedCharactersToSpace<LChar>(UCharPredicate(isWhiteSpace)); @@ -948,24 +959,54 @@ float StringImpl::toFloat(bool* ok) return charactersToFloat(characters16(), m_length, ok); } -bool equalIgnoringCase(const LChar* a, const LChar* b, unsigned length) +// Table is based on ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt +static const UChar latin1CaseFoldTable[256] = { + 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f, + 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, + 0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, + 0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f, + 0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f, + 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f, + 0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f, + 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f, + 0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f, + 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f, + 0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, 0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af, + 0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x03bc, 0x00b6, 0x00b7, 0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf, + 0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef, + 0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00d7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00df, + 0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef, + 0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff, +}; + +static inline bool equalCompatibilityCaseless(const LChar* a, const LChar* b, unsigned length) { while (length--) { - if (StringImpl::latin1CaseFoldTable[*a++] != StringImpl::latin1CaseFoldTable[*b++]) + if (latin1CaseFoldTable[*a++] != latin1CaseFoldTable[*b++]) return false; } return true; } -bool equalIgnoringCase(const UChar* a, const LChar* b, unsigned length) +static inline bool equalCompatibilityCaseless(const UChar* a, const LChar* b, unsigned length) { while (length--) { - if (u_foldCase(*a++, U_FOLD_CASE_DEFAULT) != StringImpl::latin1CaseFoldTable[*b++]) + if (u_foldCase(*a++, U_FOLD_CASE_DEFAULT) != latin1CaseFoldTable[*b++]) return false; } return true; } +static inline bool equalCompatibilityCaseless(const LChar* a, const UChar* b, unsigned length) +{ + return equalCompatibilityCaseless(b, a, length); +} + +static inline bool equalCompatibilityCaseless(const UChar* a, const UChar* b, unsigned length) +{ + return !u_memcasecmp(a, b, length, U_FOLD_CASE_DEFAULT); +} + size_t StringImpl::find(CharacterMatchFunctionPtr matchFunction, unsigned start) { if (is8Bit()) @@ -986,8 +1027,11 @@ size_t StringImpl::find(const LChar* matchString, unsigned index) return std::min(index, length()); // Optimization 1: fast case for strings of length 1. - if (matchLength == 1) + if (matchLength == 1) { + if (is8Bit()) + return WTF::find(characters8(), length(), matchString[0], index); return WTF::find(characters16(), length(), *matchString, index); + } // Check index & matchLength are in range. if (index > length()) @@ -998,10 +1042,32 @@ size_t StringImpl::find(const LChar* matchString, unsigned index) // delta is the number of additional times to test; delta == 0 means test only once. unsigned delta = searchLength - matchLength; - const UChar* searchCharacters = deprecatedCharacters() + index; - // Optimization 2: keep a running hash of the strings, // only call equal if the hashes match. + + if (is8Bit()) { + const LChar* searchCharacters = characters8() + index; + + unsigned searchHash = 0; + unsigned matchHash = 0; + for (unsigned i = 0; i < matchLength; ++i) { + searchHash += searchCharacters[i]; + matchHash += matchString[i]; + } + + unsigned i = 0; + while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) { + if (i == delta) + return notFound; + searchHash += searchCharacters[i + matchLength]; + searchHash -= searchCharacters[i]; + ++i; + } + return index + i; + } + + const UChar* searchCharacters = characters16() + index; + unsigned searchHash = 0; unsigned matchHash = 0; for (unsigned i = 0; i < matchLength; ++i) { @@ -1010,7 +1076,6 @@ size_t StringImpl::find(const LChar* matchString, unsigned index) } unsigned i = 0; - // keep looping until we match while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) { if (i == delta) return notFound; @@ -1042,45 +1107,27 @@ size_t StringImpl::findIgnoringCase(const LChar* matchString, unsigned index) // delta is the number of additional times to test; delta == 0 means test only once. unsigned delta = searchLength - matchLength; - const UChar* searchCharacters = deprecatedCharacters() + index; + if (is8Bit()) { + const LChar* searchCharacters = characters8() + index; - unsigned i = 0; - // keep looping until we match - while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) { - if (i == delta) - return notFound; - ++i; + unsigned i = 0; + while (!equalCompatibilityCaseless(searchCharacters + i, matchString, matchLength)) { + if (i == delta) + return notFound; + ++i; + } + return index + i; } - return index + i; -} - -template <typename SearchCharacterType, typename MatchCharacterType> -ALWAYS_INLINE static size_t findInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength) -{ - // Optimization: keep a running hash of the strings, - // only call equal() if the hashes match. - // delta is the number of additional times to test; delta == 0 means test only once. - unsigned delta = searchLength - matchLength; - - unsigned searchHash = 0; - unsigned matchHash = 0; - - for (unsigned i = 0; i < matchLength; ++i) { - searchHash += searchCharacters[i]; - matchHash += matchCharacters[i]; - } + const UChar* searchCharacters = characters16() + index; unsigned i = 0; - // keep looping until we match - while (searchHash != matchHash || !equal(searchCharacters + i, matchCharacters, matchLength)) { + while (!equalCompatibilityCaseless(searchCharacters + i, matchString, matchLength)) { if (i == delta) return notFound; - searchHash += searchCharacters[i + matchLength]; - searchHash -= searchCharacters[i]; ++i; } - return index + i; + return index + i; } size_t StringImpl::find(StringImpl* matchString) @@ -1128,35 +1175,7 @@ size_t StringImpl::find(StringImpl* matchString, unsigned index) if (UNLIKELY(!matchString)) return notFound; - unsigned matchLength = matchString->length(); - - // Optimization 1: fast case for strings of length 1. - if (matchLength == 1) { - if (is8Bit()) - return WTF::find(characters8(), length(), (*matchString)[0], index); - return WTF::find(characters16(), length(), (*matchString)[0], index); - } - - if (UNLIKELY(!matchLength)) - return std::min(index, length()); - - // Check index & matchLength are in range. - if (index > length()) - return notFound; - unsigned searchLength = length() - index; - if (matchLength > searchLength) - return notFound; - - if (is8Bit()) { - if (matchString->is8Bit()) - return findInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength); - return findInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength); - } - - if (matchString->is8Bit()) - return findInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength); - - return findInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength); + return findCommon(*this, *matchString, index); } template <typename SearchCharacterType, typename MatchCharacterType> @@ -1167,7 +1186,7 @@ ALWAYS_INLINE static size_t findIgnoringCaseInner(const SearchCharacterType* sea unsigned i = 0; // keep looping until we match - while (!equalIgnoringCase(searchCharacters + i, matchCharacters, matchLength)) { + while (!equalCompatibilityCaseless(searchCharacters + i, matchCharacters, matchLength)) { if (i == delta) return notFound; ++i; @@ -1203,11 +1222,28 @@ size_t StringImpl::findIgnoringCase(StringImpl* matchString, unsigned index) return findIgnoringCaseInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength); } -size_t StringImpl::findNextLineStart(unsigned index) +size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString) const { - if (is8Bit()) - return WTF::findNextLineStart(characters8(), m_length, index); - return WTF::findNextLineStart(characters16(), m_length, index); + return ::WTF::findIgnoringASCIICase(*this, matchString, 0); +} + +size_t StringImpl::findIgnoringASCIICase(const StringImpl& matchString, unsigned startOffset) const +{ + return ::WTF::findIgnoringASCIICase(*this, matchString, startOffset); +} + +size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString) const +{ + if (!matchString) + return notFound; + return ::WTF::findIgnoringASCIICase(*this, *matchString, 0); +} + +size_t StringImpl::findIgnoringASCIICase(const StringImpl* matchString, unsigned startOffset) const +{ + if (!matchString) + return notFound; + return ::WTF::findIgnoringASCIICase(*this, *matchString, startOffset); } size_t StringImpl::reverseFind(UChar c, unsigned index) @@ -1284,7 +1320,7 @@ ALWAYS_INLINE static size_t reverseFindIgnoringCaseInner(const SearchCharacterTy unsigned delta = std::min(index, length - matchLength); // keep looping until we match - while (!equalIgnoringCase(searchCharacters + delta, matchCharacters, matchLength)) { + while (!equalCompatibilityCaseless(searchCharacters + delta, matchCharacters, matchLength)) { if (!delta) return notFound; --delta; @@ -1330,26 +1366,52 @@ ALWAYS_INLINE static bool equalInner(const StringImpl* stringImpl, unsigned star return equal(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength); } if (stringImpl->is8Bit()) - return equalIgnoringCase(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength); - return equalIgnoringCase(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength); + return equalCompatibilityCaseless(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength); + return equalCompatibilityCaseless(stringImpl->characters16() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength); +} + +ALWAYS_INLINE static bool equalInner(const StringImpl& stringImpl, unsigned startOffset, const StringImpl& matchString) +{ + if (startOffset > stringImpl.length()) + return false; + if (matchString.length() > stringImpl.length()) + return false; + if (matchString.length() + startOffset > stringImpl.length()) + return false; + + if (stringImpl.is8Bit()) { + if (matchString.is8Bit()) + return equal(stringImpl.characters8() + startOffset, matchString.characters8(), matchString.length()); + return equal(stringImpl.characters8() + startOffset, matchString.characters16(), matchString.length()); + } + if (matchString.is8Bit()) + return equal(stringImpl.characters16() + startOffset, matchString.characters8(), matchString.length()); + return equal(stringImpl.characters16() + startOffset, matchString.characters16(), matchString.length()); } bool StringImpl::startsWith(const StringImpl* str) const { if (!str) return false; + return ::WTF::startsWith(*this, *str); +} - if (str->length() > length()) +bool StringImpl::startsWith(const StringImpl& str) const +{ + return ::WTF::startsWith(*this, str); +} + +bool StringImpl::startsWithIgnoringASCIICase(const StringImpl* prefix) const +{ + if (!prefix) return false; - if (is8Bit()) { - if (str->is8Bit()) - return equal(characters8(), str->characters8(), str->length()); - return equal(characters8(), str->characters16(), str->length()); - } - if (str->is8Bit()) - return equal(characters16(), str->characters8(), str->length()); - return equal(characters16(), str->characters16(), str->length()); + return ::WTF::startsWithIgnoringASCIICase(*this, *prefix); +} + +bool StringImpl::startsWithIgnoringASCIICase(const StringImpl& prefix) const +{ + return ::WTF::startsWithIgnoringASCIICase(*this, prefix); } bool StringImpl::startsWith(UChar character) const @@ -1365,6 +1427,24 @@ bool StringImpl::startsWith(const char* matchString, unsigned matchLength, bool return equalInner(this, 0, matchString, matchLength, caseSensitive); } +bool StringImpl::hasInfixStartingAt(const StringImpl& matchString, unsigned startOffset) const +{ + return equalInner(*this, startOffset, matchString); +} + +bool StringImpl::endsWith(StringImpl* suffix) +{ + if (!suffix) + return false; + + return ::WTF::endsWith(*this, *suffix); +} + +bool StringImpl::endsWith(StringImpl& suffix) +{ + return ::WTF::endsWith(*this, suffix); +} + bool StringImpl::endsWith(StringImpl* matchString, bool caseSensitive) { ASSERT(matchString); @@ -1375,6 +1455,19 @@ bool StringImpl::endsWith(StringImpl* matchString, bool caseSensitive) return false; } +bool StringImpl::endsWithIgnoringASCIICase(const StringImpl* suffix) const +{ + if (!suffix) + return false; + + return ::WTF::endsWithIgnoringASCIICase(*this, *suffix); +} + +bool StringImpl::endsWithIgnoringASCIICase(const StringImpl& suffix) const +{ + return ::WTF::endsWithIgnoringASCIICase(*this, suffix); +} + bool StringImpl::endsWith(UChar character) const { return m_length && (*this)[m_length - 1] == character; @@ -1389,7 +1482,14 @@ bool StringImpl::endsWith(const char* matchString, unsigned matchLength, bool ca return equalInner(this, startOffset, matchString, matchLength, caseSensitive); } -PassRef<StringImpl> StringImpl::replace(UChar oldC, UChar newC) +bool StringImpl::hasInfixEndingAt(const StringImpl& matchString, unsigned endOffset) const +{ + if (endOffset < matchString.length()) + return false; + return equalInner(*this, endOffset - matchString.length(), matchString); +} + +Ref<StringImpl> StringImpl::replace(UChar oldC, UChar newC) { if (oldC == newC) return *this; @@ -1450,7 +1550,7 @@ PassRef<StringImpl> StringImpl::replace(UChar oldC, UChar newC) return newImpl; } -PassRef<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str) +Ref<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str) { position = std::min(position, length()); lengthToReplace = std::min(lengthToReplace, length() - position); @@ -1495,7 +1595,7 @@ PassRef<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToRepl return newImpl; } -PassRef<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement) +Ref<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement) { if (!replacement) return *this; @@ -1506,7 +1606,7 @@ PassRef<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement) return replace(pattern, replacement->m_data16, replacement->length()); } -PassRef<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength) +Ref<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength) { ASSERT(replacement); @@ -1583,7 +1683,7 @@ PassRef<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, return newImpl; } -PassRef<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength) +Ref<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength) { ASSERT(replacement); @@ -1663,7 +1763,7 @@ PassRef<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, return newImpl; } -PassRef<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement) +Ref<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement) { if (!pattern || !replacement) return *this; @@ -1770,34 +1870,9 @@ PassRef<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replace return newImpl; } -static inline bool stringImplContentEqual(const StringImpl* a, const StringImpl* b) -{ - unsigned aLength = a->length(); - unsigned bLength = b->length(); - if (aLength != bLength) - return false; - - if (a->is8Bit()) { - if (b->is8Bit()) - return equal(a->characters8(), b->characters8(), aLength); - - return equal(a->characters8(), b->characters16(), aLength); - } - - if (b->is8Bit()) - return equal(a->characters16(), b->characters8(), aLength); - - return equal(a->characters16(), b->characters16(), aLength); -} - bool equal(const StringImpl* a, const StringImpl* b) { - if (a == b) - return true; - if (!a || !b) - return false; - - return stringImplContentEqual(a, b); + return equalCommon(a, b); } template <typename CharType> @@ -1860,109 +1935,34 @@ bool equal(const StringImpl* a, const LChar* b) return !b[length]; } -bool equalNonNull(const StringImpl* a, const StringImpl* b) +bool equal(const StringImpl& a, const StringImpl& b) { - ASSERT(a && b); - if (a == b) - return true; - - return stringImplContentEqual(a, b); + return equalCommon(a, b); } -bool equalIgnoringCase(const StringImpl* a, const StringImpl* b) +bool equalIgnoringNullity(StringImpl* a, StringImpl* b) { - if (a == b) + if (!a && b && !b->length()) return true; - if (!a || !b) - return false; - - return CaseFoldingHash::equal(a, b); -} - -bool equalIgnoringCase(const StringImpl* a, const LChar* b) -{ - if (!a) - return !b; - if (!b) - return !a; - - unsigned length = a->length(); - - // Do a faster loop for the case where all the characters are ASCII. - UChar ored = 0; - bool equal = true; - if (a->is8Bit()) { - const LChar* as = a->characters8(); - for (unsigned i = 0; i != length; ++i) { - LChar bc = b[i]; - if (!bc) - return false; - UChar ac = as[i]; - ored |= ac; - equal = equal && (toASCIILower(ac) == toASCIILower(bc)); - } - - // Do a slower implementation for cases that include non-ASCII characters. - if (ored & ~0x7F) { - equal = true; - for (unsigned i = 0; i != length; ++i) - equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT); - } - - return equal && !b[length]; - } - - const UChar* as = a->characters16(); - for (unsigned i = 0; i != length; ++i) { - LChar bc = b[i]; - if (!bc) - return false; - UChar ac = as[i]; - ored |= ac; - equal = equal && (toASCIILower(ac) == toASCIILower(bc)); - } - - // Do a slower implementation for cases that include non-ASCII characters. - if (ored & ~0x7F) { - equal = true; - for (unsigned i = 0; i != length; ++i) { - equal = equal && u_foldCase(as[i], U_FOLD_CASE_DEFAULT) == u_foldCase(b[i], U_FOLD_CASE_DEFAULT); - } - } - - return equal && !b[length]; + if (!b && a && !a->length()) + return true; + return equal(a, b); } -bool equalIgnoringCaseNonNull(const StringImpl* a, const StringImpl* b) +bool equalIgnoringASCIICase(const StringImpl* a, const StringImpl* b) { - ASSERT(a && b); if (a == b) return true; - - unsigned length = a->length(); - if (length != b->length()) + if (!a || !b) return false; - - if (a->is8Bit()) { - if (b->is8Bit()) - return equalIgnoringCase(a->characters8(), b->characters8(), length); - - return equalIgnoringCase(b->characters16(), a->characters8(), length); - } - - if (b->is8Bit()) - return equalIgnoringCase(a->characters16(), b->characters8(), length); - - return equalIgnoringCase(a->characters16(), b->characters16(), length); + return equalIgnoringASCIICaseCommon(*a, *b); } -bool equalIgnoringNullity(StringImpl* a, StringImpl* b) +bool equalIgnoringASCIICaseNonNull(const StringImpl* a, const StringImpl* b) { - if (!a && b && !b->length()) - return true; - if (!b && a && !a->length()) - return true; - return equal(a, b); + ASSERT(a); + ASSERT(b); + return equalIgnoringASCIICase(*a, *b); } UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality) @@ -1985,7 +1985,7 @@ UCharDirection StringImpl::defaultWritingDirection(bool* hasStrongDirectionality return U_LEFT_TO_RIGHT; } -PassRef<StringImpl> StringImpl::adopt(StringBuffer<LChar>& buffer) +Ref<StringImpl> StringImpl::adopt(StringBuffer<LChar>&& buffer) { unsigned length = buffer.length(); if (!length) @@ -1993,7 +1993,7 @@ PassRef<StringImpl> StringImpl::adopt(StringBuffer<LChar>& buffer) return adoptRef(*new StringImpl(buffer.release(), length)); } -PassRef<StringImpl> StringImpl::adopt(StringBuffer<UChar>& buffer) +Ref<StringImpl> StringImpl::adopt(StringBuffer<UChar>&& buffer) { unsigned length = buffer.length(); if (!length) @@ -2005,11 +2005,7 @@ size_t StringImpl::sizeInBytes() const { // FIXME: support substrings size_t size = length(); - if (is8Bit()) { - if (has16BitShadow()) { - size += 2 * size; - } - } else + if (!is8Bit()) size *= 2; return size + sizeof(*this); } @@ -2023,8 +2019,7 @@ static inline void putUTF8Triple(char*& buffer, UChar ch) *buffer++ = static_cast<char>((ch & 0x3F) | 0x80); } -bool StringImpl::utf8Impl( - const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode) +bool StringImpl::utf8Impl(const UChar* characters, unsigned length, char*& buffer, size_t bufferSize, ConversionMode mode) { if (mode == StrictConversionReplacingUnpairedSurrogatesWithFFFD) { const UChar* charactersEnd = characters + length; @@ -2075,8 +2070,21 @@ bool StringImpl::utf8Impl( return true; } -CString StringImpl::utf8ForCharacters( - const UChar* characters, unsigned length, ConversionMode mode) +CString StringImpl::utf8ForCharacters(const LChar* characters, unsigned length) +{ + if (!length) + return CString("", 0); + if (length > std::numeric_limits<unsigned>::max() / 3) + return CString(); + Vector<char, 1024> bufferVector(length * 3); + char* buffer = bufferVector.data(); + const LChar* source = characters; + ConversionResult result = convertLatin1ToUTF8(&source, source + length, &buffer, buffer + bufferVector.size()); + ASSERT_UNUSED(result, result != targetExhausted); // (length * 3) should be sufficient for any conversion + return CString(bufferVector.data(), buffer - bufferVector.data()); +} + +CString StringImpl::utf8ForCharacters(const UChar* characters, unsigned length, ConversionMode mode) { if (!length) return CString("", 0); @@ -2131,25 +2139,21 @@ CString StringImpl::utf8(ConversionMode mode) const return utf8ForRange(0, length(), mode); } -// Table is based on ftp://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt -const UChar StringImpl::latin1CaseFoldTable[256] = { - 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f, - 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017, 0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f, - 0x0020, 0x0021, 0x0022, 0x0023, 0x0024, 0x0025, 0x0026, 0x0027, 0x0028, 0x0029, 0x002a, 0x002b, 0x002c, 0x002d, 0x002e, 0x002f, - 0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f, - 0x0040, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f, - 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x005b, 0x005c, 0x005d, 0x005e, 0x005f, - 0x0060, 0x0061, 0x0062, 0x0063, 0x0064, 0x0065, 0x0066, 0x0067, 0x0068, 0x0069, 0x006a, 0x006b, 0x006c, 0x006d, 0x006e, 0x006f, - 0x0070, 0x0071, 0x0072, 0x0073, 0x0074, 0x0075, 0x0076, 0x0077, 0x0078, 0x0079, 0x007a, 0x007b, 0x007c, 0x007d, 0x007e, 0x007f, - 0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087, 0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f, - 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097, 0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f, - 0x00a0, 0x00a1, 0x00a2, 0x00a3, 0x00a4, 0x00a5, 0x00a6, 0x00a7, 0x00a8, 0x00a9, 0x00aa, 0x00ab, 0x00ac, 0x00ad, 0x00ae, 0x00af, - 0x00b0, 0x00b1, 0x00b2, 0x00b3, 0x00b4, 0x03bc, 0x00b6, 0x00b7, 0x00b8, 0x00b9, 0x00ba, 0x00bb, 0x00bc, 0x00bd, 0x00be, 0x00bf, - 0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef, - 0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00d7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00df, - 0x00e0, 0x00e1, 0x00e2, 0x00e3, 0x00e4, 0x00e5, 0x00e6, 0x00e7, 0x00e8, 0x00e9, 0x00ea, 0x00eb, 0x00ec, 0x00ed, 0x00ee, 0x00ef, - 0x00f0, 0x00f1, 0x00f2, 0x00f3, 0x00f4, 0x00f5, 0x00f6, 0x00f7, 0x00f8, 0x00f9, 0x00fa, 0x00fb, 0x00fc, 0x00fd, 0x00fe, 0x00ff, -}; - +bool equalIgnoringNullity(const UChar* a, size_t aLength, StringImpl* b) +{ + if (!b) + return !aLength; + if (aLength != b->length()) + return false; + if (b->is8Bit()) { + const LChar* bCharacters = b->characters8(); + for (unsigned i = 0; i < aLength; ++i) { + if (a[i] != bCharacters[i]) + return false; + } + return true; + } + return !memcmp(a, b->characters16(), b->length() * sizeof(UChar)); +} } // namespace WTF |