/*

* 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) 2006 Andrew Wellington (proton@wiretapped.net)

*

* This library is free software; you can redistribute it and/or

* modify it under the terms of the GNU Library General Public

* License as published by the Free Software Foundation; either

* version 2 of the License, or (at your option) any later version.

*

* This library is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

* Library General Public License for more details.

*

* You should have received a copy of the GNU Library General Public License

* along with this library; see the file COPYING.LIB. If not, write to

* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

* Boston, MA 02110-1301, USA.

*

*/

#include "config.h"

#include "StringImpl.h"

#include "AtomicString.h"

#include "StringBuffer.h"

#include "StringHash.h"

#include <wtf/ProcessID.h>

#include <wtf/StdLibExtras.h>

#include <wtf/WTFThreadData.h>

#include <wtf/text/CString.h>

#include <wtf/unicode/CharacterNames.h>

#include <wtf/unicode/UTF8.h>

#ifdef STRING_STATS

#include <unistd.h>

#include <wtf/DataLog.h>

#endif

using namespace std;

namespace WTF {

using namespace Unicode;

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

#ifdef STRING_STATS

StringStats StringImpl::m_stringStats;

unsigned StringStats::s_stringRemovesTillPrintStats = StringStats::s_printStringStatsFrequency;

void StringStats::removeString(StringImpl* string)

{

unsigned length = string->length();

bool isSubString = string->isSubString();

--m_totalNumberStrings;

if (string->has16BitShadow()) {

--m_numberUpconvertedStrings;

if (!isSubString)

m_totalUpconvertedData -= length;

}

if (string->is8Bit()) {

--m_number8BitStrings;

if (!isSubString)

m_total8BitData -= length;

} else {

--m_number16BitStrings;

if (!isSubString)

m_total16BitData -= length;

}

if (!--s_stringRemovesTillPrintStats) {

s_stringRemovesTillPrintStats = s_printStringStatsFrequency;

printStats();

}

}

void StringStats::printStats()

{

dataLogF("String stats for process id %d:\n", getCurrentProcessID());

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);

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);

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;

double percentSavings = totalSavedBytes ? ((double)totalSavedBytes * 100) / (double)(totalDataBytes + totalSavedBytes) : 0.0;

dataLogF(" Total savings %12llu bytes (%5.2f%%)\n", totalSavedBytes, percentSavings);

}

#endif

StringImpl::~StringImpl()

{

ASSERT(!isStatic());

STRING_STATS_REMOVE_STRING(this);

if (isAtomic())

AtomicString::remove(this);

if (isIdentifier()) {

if (!wtfThreadData().currentIdentifierTable()->remove(this))

CRASH();

}

BufferOwnership ownership = bufferOwnership();

if (has16BitShadow()) {

ASSERT(m_copyData16);

fastFree(m_copyData16);

}

if (ownership == BufferInternal)

return;

if (ownership == BufferOwned) {

// We use m_data8, but since it is a union with m_data16 this works either way.

ASSERT(m_data8);

fastFree(const_cast<LChar*>(m_data8));

return;

}

ASSERT(ownership == BufferSubstring);

ASSERT(m_substringBuffer);

m_substringBuffer->deref();

}

void StringImpl::destroy(StringImpl* stringImpl)

{

stringImpl->~StringImpl();

fastFree(stringImpl);

}

PassRef<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)

{

return createFromLiteral(characters, strlen(characters));

}

PassRef<StringImpl> StringImpl::createWithoutCopying(const UChar* characters, unsigned length)

{

if (!length)

return *empty();

return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));

}

PassRef<StringImpl> StringImpl::createWithoutCopying(const LChar* characters, unsigned length)

{

if (!length)

return *empty();

return adoptRef(*new StringImpl(characters, length, ConstructWithoutCopying));

}

template <typename CharType>

inline PassRef<StringImpl> StringImpl::createUninitializedInternal(unsigned length, CharType*& data)

{

if (!length) {

data = 0;

return *empty();

}

return createUninitializedInternalNonEmpty(length, data);

}

template <typename CharType>

inline PassRef<StringImpl> StringImpl::createUninitializedInternalNonEmpty(unsigned length, CharType*& data)

{

ASSERT(length);

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

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

// 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));

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

return constructInternal<CharType>(string, length);

}

PassRef<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data)

{

return createUninitializedInternal(length, data);

}

PassRef<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)

{

ASSERT(originalString->hasOneRef());

ASSERT(originalString->bufferOwnership() == BufferInternal);

if (!length) {

data = 0;

return *empty();

}

// 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));

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

return constructInternal<CharType>(string, length);

}

PassRef<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, LChar*& data)

{

ASSERT(originalString->is8Bit());

return reallocateInternal(originalString, length, data);

}

PassRef<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, UChar*& data)

{

ASSERT(!originalString->is8Bit());

return reallocateInternal(originalString, length, data);

}

template <typename CharType>

inline PassRef<StringImpl> StringImpl::createInternal(const CharType* characters, unsigned length)

{

if (!characters || !length)

return *empty();

CharType* data;

auto string = createUninitializedInternalNonEmpty(length, data);

memcpy(data, characters, length * sizeof(CharType));

return string;

}

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

{

return createInternal(characters, length);

}

PassRef<StringImpl> StringImpl::create(const LChar* characters, unsigned length)

{

return createInternal(characters, length);

}

PassRef<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length)

{

if (!characters || !length)

return *empty();

LChar* data;

RefPtr<StringImpl> string = createUninitializedInternalNonEmpty(length, data);

for (size_t i = 0; i < length; ++i) {

if (characters[i] & 0xff00)

return create(characters, length);

data[i] = static_cast<LChar>(characters[i]);

}

return string.releaseNonNull();

}

PassRef<StringImpl> StringImpl::create8BitIfPossible(const UChar* string)

{

return StringImpl::create8BitIfPossible(string, lengthOfNullTerminatedString(string));

}

PassRef<StringImpl> StringImpl::create(const LChar* string)

{

if (!string)

return *empty();

size_t length = strlen(reinterpret_cast<const char*>(string));

if (length > numeric_limits<unsigned>::max())

CRASH();

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->characters() + 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

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

// that's a problem in practice.

if (is8Bit()) {

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

UChar c = m_data8[i];

if (!isASCIISpace(c))

return false;

}

return true;

}

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

UChar c = m_data16[i];

if (!isASCIISpace(c))

return false;

}

return true;

}

PassRef<StringImpl> StringImpl::substring(unsigned start, unsigned length)

{

if (start >= m_length)

return *empty();

unsigned maxLength = m_length - start;

if (length >= maxLength) {

if (!start)

return *this;

length = maxLength;

}

if (is8Bit())

return create(m_data8 + start, length);

return create(m_data16 + start, length);

}

UChar32 StringImpl::characterStartingAt(unsigned i)

{

if (is8Bit())

return m_data8[i];

if (U16_IS_SINGLE(m_data16[i]))

return m_data16[i];

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

return U16_GET_SUPPLEMENTARY(m_data16[i], m_data16[i + 1]);

return 0;

}

PassRef<StringImpl> StringImpl::lower()

{

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

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

// 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));

}

}

return newImpl;

}

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;

}

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

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

return *this;

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

UChar* data16;

auto newImpl = createUninitializedInternalNonEmpty(m_length, data16);

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

UChar c = m_data16[i];

data16[i] = toASCIILower(c);

}

return newImpl;

}

if (m_length > static_cast<unsigned>(numeric_limits<int32_t>::max()))

CRASH();

int32_t length = m_length;

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

UChar* data16;

RefPtr<StringImpl> 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();

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();

}

PassRef<StringImpl> StringImpl::upper()

{

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

if (m_length > static_cast<unsigned>(numeric_limits<int32_t>::max()))

CRASH();

int32_t length = m_length;

if (is8Bit()) {

LChar* data8;

RefPtr<StringImpl> 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();

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

// 2. Lower case sharp-S converts to "SS" (two characters)

for (int32_t i = 0; i < length; ++i) {

LChar c = m_data8[i];

if (UNLIKELY(c == smallLetterSharpS))

++numberSharpSCharacters;

ASSERT(u_toupper(c) <= 0xFFFF);

UChar upper = u_toupper(c);

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;

}

data8[i] = static_cast<LChar>(upper);

}

if (!numberSharpSCharacters)

return newImpl.releaseNonNull();

// We have numberSSCharacters sharp-s characters, but none of the other special characters.

newImpl = createUninitialized(m_length + numberSharpSCharacters, data8);

LChar* dest = data8;

for (int32_t i = 0; i < length; ++i) {

LChar c = m_data8[i];

if (c == smallLetterSharpS) {

*dest++ = 'S';

*dest++ = 'S';

} else {

ASSERT(u_toupper(c) <= 0xFF);

*dest++ = static_cast<LChar>(u_toupper(c));

}

}

return newImpl.releaseNonNull();

}

upconvert:

const UChar* source16 = characters();

UChar* data16;

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

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

unsigned ored = 0;

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

UChar c = source16[i];

ored |= c;

data16[i] = toASCIIUpper(c);

}

if (!(ored & ~0x7F))

return newImpl.releaseNonNull();

// 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();

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();

}

static inline bool needsTurkishCasingRules(const AtomicString& localeIdentifier)

{

// Either "tr" or "az" locale, with case sensitive comparison and allowing for an ignored subtag.

UChar first = localeIdentifier[0];

UChar second = localeIdentifier[1];

return ((isASCIIAlphaCaselessEqual(first, 't') && isASCIIAlphaCaselessEqual(second, 'r'))

|| (isASCIIAlphaCaselessEqual(first, 'a') && isASCIIAlphaCaselessEqual(second, 'z')))

&& (localeIdentifier.length() == 2 || localeIdentifier[2] == '-');

}

PassRef<StringImpl> StringImpl::lower(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();

// 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

// just like the end of that function.

if (m_length > static_cast<unsigned>(numeric_limits<int32_t>::max()))

CRASH();

int length = m_length;

// 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 = characters();

UChar* data16;

RefPtr<StringImpl> 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();

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();

}

PassRef<StringImpl> StringImpl::upper(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();

if (m_length > static_cast<unsigned>(numeric_limits<int32_t>::max()))

CRASH();

int length = m_length;

// 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 = characters();

UChar* data16;

RefPtr<StringImpl> 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();

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;

}

PassRef<StringImpl> StringImpl::foldCase()

{

if (m_length > static_cast<unsigned>(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;

}

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]));

}

return newImpl;

}

// 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();

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

UErrorCode status = U_ZERO_ERROR;

int32_t realLength = u_strFoldCase(data, length, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);

if (U_SUCCESS(status) && realLength == length)

return newImpl.releaseNonNull();

newImpl = createUninitialized(realLength, data);

status = U_ZERO_ERROR;

u_strFoldCase(data, realLength, m_data16, m_length, U_FOLD_CASE_DEFAULT, &status);

if (U_FAILURE(status))

return *this;

return newImpl.releaseNonNull();

}

template <class UCharPredicate>

inline PassRef<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate)

{

if (!m_length)

return *this;

unsigned start = 0;

unsigned end = m_length - 1;

// skip white space from start

while (start <= end && predicate(is8Bit() ? m_data8[start] : m_data16[start]))

++start;

// only white space

if (start > end)

return *empty();

// skip white space from end

while (end && predicate(is8Bit() ? m_data8[end] : m_data16[end]))

--end;

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

return *this;

if (is8Bit())

return create(m_data8 + start, end + 1 - start);

return create(m_data16 + start, end + 1 - start);

}

class UCharPredicate {

public:

inline UCharPredicate(CharacterMatchFunctionPtr function): m_function(function) { }

inline bool operator()(UChar ch) const

{

return m_function(ch);

}

private:

const CharacterMatchFunctionPtr m_function;

};

class SpaceOrNewlinePredicate {

public:

inline bool operator()(UChar ch) const

{

return isSpaceOrNewline(ch);

}

};

PassRef<StringImpl> StringImpl::stripWhiteSpace()

{

return stripMatchedCharacters(SpaceOrNewlinePredicate());

}

PassRef<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)

{

return stripMatchedCharacters(UCharPredicate(isWhiteSpace));

}

template <typename CharType>

ALWAYS_INLINE PassRef<StringImpl> StringImpl::removeCharacters(const CharType* characters, CharacterMatchFunctionPtr findMatch)

{

const CharType* from = characters;

const CharType* fromend = from + m_length;

// Assume the common case will not remove any characters

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

++from;

if (from == fromend)

return *this;

StringBuffer<CharType> data(m_length);

CharType* to = data.characters();

unsigned outc = from - characters;

if (outc)

memcpy(to, characters, outc * sizeof(CharType));

while (true) {

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

++from;

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

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

if (from == fromend)

break;

}

data.shrink(outc);

return adopt(data);

}

PassRef<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)

{

if (is8Bit())

return removeCharacters(characters8(), findMatch);

return removeCharacters(characters16(), findMatch);

}

template <typename CharType, class UCharPredicate>

inline PassRef<StringImpl> StringImpl::simplifyMatchedCharactersToSpace(UCharPredicate predicate)

{

StringBuffer<CharType> data(m_length);

const CharType* from = getCharacters<CharType>();

const CharType* fromend = from + m_length;

int outc = 0;

bool changedToSpace = false;

CharType* to = data.characters();

while (true) {

while (from != fromend && predicate(*from)) {

if (*from != ' ')

changedToSpace = true;

++from;

}

while (from != fromend && !predicate(*from))

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

if (from != fromend)

to[outc++] = ' ';

else

break;

}

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

--outc;

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

return *this;

data.shrink(outc);

return adopt(data);

}

PassRef<StringImpl> StringImpl::simplifyWhiteSpace()

{

if (is8Bit())

return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate());

return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate());

}

PassRef<StringImpl> StringImpl::simplifyWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)

{

if (is8Bit())

return StringImpl::simplifyMatchedCharactersToSpace<LChar>(UCharPredicate(isWhiteSpace));

return StringImpl::simplifyMatchedCharactersToSpace<UChar>(UCharPredicate(isWhiteSpace));

}

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

{

if (is8Bit())

return charactersToIntStrict(characters8(), m_length, ok, base);

return charactersToIntStrict(characters16(), m_length, ok, base);

}

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

{

if (is8Bit())

return charactersToUIntStrict(characters8(), m_length, ok, base);

return charactersToUIntStrict(characters16(), m_length, ok, base);

}

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

{

if (is8Bit())

return charactersToInt64Strict(characters8(), m_length, ok, base);

return charactersToInt64Strict(characters16(), m_length, ok, base);

}

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

{

if (is8Bit())

return charactersToUInt64Strict(characters8(), m_length, ok, base);

return charactersToUInt64Strict(characters16(), m_length, ok, base);

}

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

{

if (is8Bit())

return charactersToIntPtrStrict(characters8(), m_length, ok, base);

return charactersToIntPtrStrict(characters16(), m_length, ok, base);

}

int StringImpl::toInt(bool* ok)

{

if (is8Bit())

return charactersToInt(characters8(), m_length, ok);

return charactersToInt(characters16(), m_length, ok);

}

unsigned StringImpl::toUInt(bool* ok)

{

if (is8Bit())

return charactersToUInt(characters8(), m_length, ok);

return charactersToUInt(characters16(), m_length, ok);

}

int64_t StringImpl::toInt64(bool* ok)

{

if (is8Bit())

return charactersToInt64(characters8(), m_length, ok);

return charactersToInt64(characters16(), m_length, ok);

}

uint64_t StringImpl::toUInt64(bool* ok)

{

if (is8Bit())

return charactersToUInt64(characters8(), m_length, ok);

return charactersToUInt64(characters16(), m_length, ok);

}

intptr_t StringImpl::toIntPtr(bool* ok)

{

if (is8Bit())

return charactersToIntPtr(characters8(), m_length, ok);

return charactersToIntPtr(characters16(), m_length, ok);

}

double StringImpl::toDouble(bool* ok)

{

if (is8Bit())

return charactersToDouble(characters8(), m_length, ok);

return charactersToDouble(characters16(), m_length, ok);

}

float StringImpl::toFloat(bool* ok)

{

if (is8Bit())

return charactersToFloat(characters8(), m_length, ok);

return charactersToFloat(characters16(), m_length, ok);

}

bool equalIgnoringCase(const LChar* a, const LChar* b, unsigned length)

{

while (length--) {

if (StringImpl::latin1CaseFoldTable[*a++] != StringImpl::latin1CaseFoldTable[*b++])

return false;

}

return true;

}

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

{

while (length--) {

if (u_foldCase(*a++, U_FOLD_CASE_DEFAULT) != StringImpl::latin1CaseFoldTable[*b++])

return false;

}

return true;

}

size_t StringImpl::find(CharacterMatchFunctionPtr matchFunction, unsigned start)

{

if (is8Bit())

return WTF::find(characters8(), m_length, matchFunction, start);

return WTF::find(characters16(), m_length, matchFunction, start);

}

size_t StringImpl::find(const LChar* matchString, unsigned index)

{

// Check for null or empty string to match against

if (!matchString)

return notFound;

size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));

if (matchStringLength > numeric_limits<unsigned>::max())

CRASH();

unsigned matchLength = matchStringLength;

if (!matchLength)

return min(index, length());

// Optimization 1: fast case for strings of length 1.

if (matchLength == 1)

return WTF::find(characters16(), length(), *matchString, index);

// Check index & matchLength are in range.

if (index > length())

return notFound;

unsigned searchLength = length() - index;

if (matchLength > searchLength)

return notFound;

// delta is the number of additional times to test; delta == 0 means test only once.