/*
 * 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 "wtf/text/StringImpl.h"

#include "wtf/LeakAnnotations.h"
#include "wtf/StdLibExtras.h"
#include "wtf/text/AtomicString.h"
#include "wtf/text/StringBuffer.h"
#include "wtf/text/StringHash.h"
#include "wtf/unicode/CharacterNames.h"

#ifdef STRING_STATS
#include "wtf/DataLog.h"
#include "wtf/MainThread.h"
#include "wtf/ProcessID.h"
#include "wtf/RefCounted.h"
#include <unistd.h>
#endif

using namespace std;

namespace WTF {

using namespace Unicode;

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

#ifdef STRING_STATS

static Mutex& statsMutex()
{
    DEFINE_STATIC_LOCAL(Mutex, mutex, ());
    return mutex;
}

static HashSet<void*>& liveStrings()
{
    // Notice that we can't use HashSet<StringImpl*> because then HashSet would dedup identical strings.
    DEFINE_STATIC_LOCAL(HashSet<void*>, strings, ());
    return strings;
}

void addStringForStats(StringImpl* string)
{
    MutexLocker locker(statsMutex());
    liveStrings().add(string);
}

void removeStringForStats(StringImpl* string)
{
    MutexLocker locker(statsMutex());
    liveStrings().remove(string);
}

static void fillWithSnippet(const StringImpl* string, Vector<char>& snippet)
{
    const unsigned kMaxSnippetLength = 64;
    snippet.clear();

    size_t expectedLength = std::min(string->length(), kMaxSnippetLength);
    if (expectedLength == kMaxSnippetLength)
        expectedLength += 3; // For the "...".
    ++expectedLength; // For the terminating '\0'.
    snippet.reserveCapacity(expectedLength);

    size_t i;
    for (i = 0; i < string->length() && i < kMaxSnippetLength; ++i) {
        UChar c = (*string)[i];
        if (isASCIIPrintable(c))
            snippet.append(c);
        else
            snippet.append('?');
    }
    if (i < string->length()) {
        snippet.append('.');
        snippet.append('.');
        snippet.append('.');
    }
    snippet.append('\0');
}

static bool isUnnecessarilyWide(const StringImpl* string)
{
    if (string->is8Bit())
        return false;
    UChar c = 0;
    for (unsigned i = 0; i < string->length(); ++i)
        c |= (*string)[i] >> 8;
    return !c;
}

class PerStringStats : public RefCounted<PerStringStats> {
public:
    static PassRefPtr<PerStringStats> create()
    {
        return adoptRef(new PerStringStats);
    }

    void add(const StringImpl* string)
    {
        ++m_numberOfCopies;
        if (!m_length) {
            m_length = string->length();
            fillWithSnippet(string, m_snippet);
        }
        if (string->isAtomic())
            ++m_numberOfAtomicCopies;
        if (isUnnecessarilyWide(string))
            m_unnecessarilyWide = true;
    }

    size_t totalCharacters() const
    {
        return m_numberOfCopies * m_length;
    }

    void print()
    {
        const char* status = "ok";
        if (m_unnecessarilyWide)
            status = "16";
        dataLogF("%8u copies (%s) of length %8u %s\n", m_numberOfCopies, status, m_length, m_snippet.data());
    }

    bool m_unnecessarilyWide;
    unsigned m_numberOfCopies;
    unsigned m_length;
    unsigned m_numberOfAtomicCopies;
    Vector<char> m_snippet;

private:
    PerStringStats()
        : m_unnecessarilyWide(false)
        , m_numberOfCopies(0)
        , m_length(0)
        , m_numberOfAtomicCopies(0)
    {
    }
};

bool operator<(const RefPtr<PerStringStats>& a, const RefPtr<PerStringStats>& b)
{
    if (a->m_unnecessarilyWide != b->m_unnecessarilyWide)
        return !a->m_unnecessarilyWide && b->m_unnecessarilyWide;
    if (a->totalCharacters() != b->totalCharacters())
        return a->totalCharacters() < b->totalCharacters();
    if (a->m_numberOfCopies != b->m_numberOfCopies)
        return a->m_numberOfCopies < b->m_numberOfCopies;
    if (a->m_length != b->m_length)
        return a->m_length < b->m_length;
    return a->m_numberOfAtomicCopies < b->m_numberOfAtomicCopies;
}

static void printLiveStringStats(void*)
{
    MutexLocker locker(statsMutex());
    HashSet<void*>& strings = liveStrings();

    HashMap<StringImpl*, RefPtr<PerStringStats> > stats;
    for (HashSet<void*>::iterator iter = strings.begin(); iter != strings.end(); ++iter) {
        StringImpl* string = static_cast<StringImpl*>(*iter);
        HashMap<StringImpl*, RefPtr<PerStringStats> >::iterator entry = stats.find(string);
        RefPtr<PerStringStats> value = entry == stats.end() ? RefPtr<PerStringStats>(PerStringStats::create()) : entry->value;
        value->add(string);
        stats.set(string, value.release());
    }

    Vector<RefPtr<PerStringStats> > all;
    for (HashMap<StringImpl*, RefPtr<PerStringStats> >::iterator iter = stats.begin(); iter != stats.end(); ++iter)
        all.append(iter->value);

    std::sort(all.begin(), all.end());
    std::reverse(all.begin(), all.end());
    for (size_t i = 0; i < 20 && i < all.size(); ++i)
        all[i]->print();
}

StringStats StringImpl::m_stringStats;

unsigned StringStats::s_stringRemovesTillPrintStats = StringStats::s_printStringStatsFrequency;

void StringStats::removeString(StringImpl* string)
{
    unsigned length = string->length();
    --m_totalNumberStrings;

    if (string->is8Bit()) {
        --m_number8BitStrings;
        m_total8BitData -= length;
    } else {
        --m_number16BitStrings;
        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 averageLength = m_totalNumberStrings ? (double)totalNumberCharacters / (double)m_totalNumberStrings : 0.0;
    unsigned long long totalDataBytes = m_total8BitData + m_total16BitData * 2;
    dataLogF("%8u Total                 %12llu chars  %12llu bytes  avg length %6.1f\n", m_totalNumberStrings, 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);

    unsigned totalOverhead = m_totalNumberStrings * sizeof(StringImpl);
    double overheadPercent = (double)totalOverhead / (double)totalDataBytes * 100;
    dataLogF("         StringImpl overheader: %8u (%5.2f%%)\n", totalOverhead, overheadPercent);

    callOnMainThread(printLiveStringStats, 0);
}
#endif


inline StringImpl::~StringImpl()
{
    ASSERT(!isStatic());

    STRING_STATS_REMOVE_STRING(this);

    if (isAtomic())
        AtomicString::remove(this);
}

void StringImpl::destroyIfNotStatic()
{
    if (!isStatic())
        delete this;
}

PassRefPtr<StringImpl> StringImpl::createUninitialized(unsigned length, LChar*& data)
{
    if (!length) {
        data = 0;
        return empty();
    }

    // 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.
    RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(LChar)));
    size_t size = sizeof(StringImpl) + length * sizeof(LChar);
    StringImpl* string = static_cast<StringImpl*>(fastMalloc(size));

    data = reinterpret_cast<LChar*>(string + 1);
    return adoptRef(new (NotNull, string) StringImpl(length, Force8BitConstructor));
}

PassRefPtr<StringImpl> StringImpl::createUninitialized(unsigned length, UChar*& data)
{
    if (!length) {
        data = 0;
        return empty();
    }

    // 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.
    RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(UChar)));
    size_t size = sizeof(StringImpl) + length * sizeof(UChar);
    StringImpl* string = static_cast<StringImpl*>(fastMalloc(size));

    data = reinterpret_cast<UChar*>(string + 1);
    return adoptRef(new (NotNull, string) StringImpl(length));
}

PassRefPtr<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, LChar*& data)
{
    ASSERT(originalString->is8Bit());
    ASSERT(originalString->hasOneRef());

    if (!length) {
        data = 0;
        return empty();
    }

    // Same as createUninitialized() except here we use fastRealloc.
    RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(LChar)));
    size_t size = sizeof(StringImpl) + length * sizeof(LChar);
    originalString->~StringImpl();
    StringImpl* string = static_cast<StringImpl*>(fastRealloc(originalString.leakRef(), size));

    data = reinterpret_cast<LChar*>(string + 1);
    return adoptRef(new (NotNull, string) StringImpl(length, Force8BitConstructor));
}

PassRefPtr<StringImpl> StringImpl::reallocate(PassRefPtr<StringImpl> originalString, unsigned length, UChar*& data)
{
    ASSERT(!originalString->is8Bit());
    ASSERT(originalString->hasOneRef());

    if (!length) {
        data = 0;
        return empty();
    }

    // Same as createUninitialized() except here we use fastRealloc.
    RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(UChar)));
    size_t size = sizeof(StringImpl) + length * sizeof(UChar);
    originalString->~StringImpl();
    StringImpl* string = static_cast<StringImpl*>(fastRealloc(originalString.leakRef(), size));

    data = reinterpret_cast<UChar*>(string + 1);
    return adoptRef(new (NotNull, string) StringImpl(length));
}

StringImpl* StringImpl::createStatic(const char* string, unsigned length, unsigned hash)
{
    ASSERT(string);
    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.
    RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(LChar)));
    size_t size = sizeof(StringImpl) + length * sizeof(LChar);
    WTF_ANNOTATE_SCOPED_MEMORY_LEAK;
    StringImpl* impl = static_cast<StringImpl*>(fastMalloc(size));

    LChar* data = reinterpret_cast<LChar*>(impl + 1);
    impl = new (NotNull, impl) StringImpl(length, hash, StaticString);
    memcpy(data, string, length * sizeof(LChar));
#ifndef NDEBUG
    impl->assertHashIsCorrect();
#endif
    return impl;
}

PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length)
{
    if (!characters || !length)
        return empty();

    UChar* data;
    RefPtr<StringImpl> string = createUninitialized(length, data);
    memcpy(data, characters, length * sizeof(UChar));
    return string.release();
}

PassRefPtr<StringImpl> StringImpl::create(const LChar* characters, unsigned length)
{
    if (!characters || !length)
        return empty();

    LChar* data;
    RefPtr<StringImpl> string = createUninitialized(length, data);
    memcpy(data, characters, length * sizeof(LChar));
    return string.release();
}

PassRefPtr<StringImpl> StringImpl::create8BitIfPossible(const UChar* characters, unsigned length)
{
    if (!characters || !length)
        return empty();

    LChar* data;
    RefPtr<StringImpl> string = createUninitialized(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.release();
}

PassRefPtr<StringImpl> StringImpl::create(const LChar* string)
{
    if (!string)
        return empty();
    size_t length = strlen(reinterpret_cast<const char*>(string));
    RELEASE_ASSERT(length <= numeric_limits<unsigned>::max());
    return create(string, length);
}

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 = characters8()[i];
            if (!isASCIISpace(c))
                return false;
        }

        return true;
    }

    for (unsigned i = 0; i < m_length; ++i) {
        UChar c = characters16()[i];
        if (!isASCIISpace(c))
            return false;
    }
    return true;
}

PassRefPtr<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(characters8() + start, length);

    return create(characters16() + start, length);
}

UChar32 StringImpl::characterStartingAt(unsigned i)
{
    if (is8Bit())
        return characters8()[i];
    if (U16_IS_SINGLE(characters16()[i]))
        return characters16()[i];
    if (i + 1 < m_length && U16_IS_LEAD(characters16()[i]) && U16_IS_TRAIL(characters16()[i + 1]))
        return U16_GET_SUPPLEMENTARY(characters16()[i], characters16()[i + 1]);
    return 0;
}

PassRefPtr<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:
    bool noUpper = true;
    UChar ored = 0;
    if (is8Bit()) {
        const LChar* end = characters8() + m_length;
        for (const LChar* chp = characters8(); chp != end; ++chp) {
            if (UNLIKELY(isASCIIUpper(*chp)))
                noUpper = false;
            ored |= *chp;
        }
        // Nothing to do if the string is all ASCII with no uppercase.
        if (noUpper && !(ored & ~0x7F))
            return this;

        RELEASE_ASSERT(m_length <= static_cast<unsigned>(numeric_limits<int32_t>::max()));
        int32_t length = m_length;

        LChar* data8;
        RefPtr<StringImpl> newImpl = createUninitialized(length, data8);

        if (!(ored & ~0x7F)) {
            for (int32_t i = 0; i < length; ++i)
                data8[i] = toASCIILower(characters8()[i]);

            return newImpl.release();
        }

        // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
        for (int32_t i = 0; i < length; ++i)
            data8[i] = static_cast<LChar>(Unicode::toLower(characters8()[i]));

        return newImpl.release();
    }

    const UChar* end = characters16() + m_length;
    for (const UChar* chp = characters16(); chp != end; ++chp) {
        if (UNLIKELY(isASCIIUpper(*chp)))
            noUpper = false;
        ored |= *chp;
    }
    // Nothing to do if the string is all ASCII with no uppercase.
    if (noUpper && !(ored & ~0x7F))
        return this;

    RELEASE_ASSERT(m_length <= static_cast<unsigned>(numeric_limits<int32_t>::max()));
    int32_t length = m_length;

    if (!(ored & ~0x7F)) {
        UChar* data16;
        RefPtr<StringImpl> newImpl = createUninitialized(m_length, data16);

        for (int32_t i = 0; i < length; ++i) {
            UChar c = characters16()[i];
            data16[i] = toASCIILower(c);
        }
        return newImpl.release();
    }

    // Do a slower implementation for cases that include non-ASCII characters.
    UChar* data16;
    RefPtr<StringImpl> newImpl = createUninitialized(m_length, data16);

    bool error;
    int32_t realLength = Unicode::toLower(data16, length, characters16(), m_length, &error);
    if (!error && realLength == length)
        return newImpl.release();

    newImpl = createUninitialized(realLength, data16);
    Unicode::toLower(data16, realLength, characters16(), m_length, &error);
    if (error)
        return this;
    return newImpl.release();
}

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

    RELEASE_ASSERT(m_length <= static_cast<unsigned>(numeric_limits<int32_t>::max()));
    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.
        LChar ored = 0;
        for (int i = 0; i < length; ++i) {
            LChar c = characters8()[i];
            ored |= c;
            data8[i] = toASCIIUpper(c);
        }
        if (!(ored & ~0x7F))
            return newImpl.release();

        // 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 = characters8()[i];
            if (UNLIKELY(c == smallLetterSharpS))
                ++numberSharpSCharacters;
            UChar upper = Unicode::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.release();

        // 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 = characters8()[i];
            if (c == smallLetterSharpS) {
                *dest++ = 'S';
                *dest++ = 'S';
            } else
                *dest++ = static_cast<LChar>(Unicode::toUpper(c));
        }

        return newImpl.release();
    }

upconvert:
    const UChar* source16 = 0;
    RefPtr<StringImpl> upconverted;
    if (is8Bit()) {
        upconverted = String::make16BitFrom8BitSource(characters8(), m_length).impl();
        source16 = upconverted->characters16();
    } else {
        source16 = characters16();
    }

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

    // Do a faster loop for the case where all the characters are ASCII.
    UChar ored = 0;
    for (int i = 0; i < length; ++i) {
        UChar c = source16[i];
        ored |= c;
        data16[i] = toASCIIUpper(c);
    }
    if (!(ored & ~0x7F))
        return newImpl.release();

    // Do a slower implementation for cases that include non-ASCII characters.
    bool error;
    newImpl = createUninitialized(m_length, data16);
    int32_t realLength = Unicode::toUpper(data16, length, source16, m_length, &error);
    if (!error && realLength == length)
        return newImpl;
    newImpl = createUninitialized(realLength, data16);
    Unicode::toUpper(data16, realLength, source16, m_length, &error);
    if (error)
        return this;
    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::fill(UChar character)
{
    if (!m_length)
        return this;

    if (!(character & ~0x7F)) {
        LChar* data;
        RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
        for (unsigned i = 0; i < m_length; ++i)
            data[i] = character;
        return newImpl.release();
    }
    UChar* data;
    RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);
    for (unsigned i = 0; i < m_length; ++i)
        data[i] = character;
    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::foldCase()
{
    RELEASE_ASSERT(m_length <= static_cast<unsigned>(numeric_limits<int32_t>::max()));
    int32_t length = m_length;

    if (is8Bit()) {
        // Do a faster loop for the case where all the characters are ASCII.
        LChar* data;
        RefPtr <StringImpl>newImpl = createUninitialized(m_length, data);
        LChar ored = 0;

        for (int32_t i = 0; i < length; ++i) {
            LChar c = characters8()[i];
            data[i] = toASCIILower(c);
            ored |= c;
        }

        if (!(ored & ~0x7F))
            return newImpl.release();

        // Do a slower implementation for cases that include non-ASCII Latin-1 characters.
        for (int32_t i = 0; i < length; ++i)
            data[i] = static_cast<LChar>(Unicode::toLower(characters8()[i]));

        return newImpl.release();
    }

    // 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 = characters16()[i];
        ored |= c;
        data[i] = toASCIILower(c);
    }
    if (!(ored & ~0x7F))
        return newImpl.release();

    // Do a slower implementation for cases that include non-ASCII characters.
    bool error;
    int32_t realLength = Unicode::foldCase(data, length, characters16(), m_length, &error);
    if (!error && realLength == length)
        return newImpl.release();
    newImpl = createUninitialized(realLength, data);
    Unicode::foldCase(data, realLength, characters16(), m_length, &error);
    if (error)
        return this;
    return newImpl.release();
}

template <class UCharPredicate>
inline PassRefPtr<StringImpl> StringImpl::stripMatchedCharacters(UCharPredicate predicate)
{
    if (!m_length)
        return empty();

    unsigned start = 0;
    unsigned end = m_length - 1;

    // skip white space from start
    while (start <= end && predicate(is8Bit() ? characters8()[start] : characters16()[start]))
        ++start;

    // only white space
    if (start > end)
        return empty();

    // skip white space from end
    while (end && predicate(is8Bit() ? characters8()[end] : characters16()[end]))
        --end;

    if (!start && end == m_length - 1)
        return this;
    if (is8Bit())
        return create(characters8() + start, end + 1 - start);
    return create(characters16() + 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);
    }
};

PassRefPtr<StringImpl> StringImpl::stripWhiteSpace()
{
    return stripMatchedCharacters(SpaceOrNewlinePredicate());
}

PassRefPtr<StringImpl> StringImpl::stripWhiteSpace(IsWhiteSpaceFunctionPtr isWhiteSpace)
{
    return stripMatchedCharacters(UCharPredicate(isWhiteSpace));
}

template <typename CharType>
ALWAYS_INLINE PassRefPtr<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 data.release();
}

PassRefPtr<StringImpl> StringImpl::removeCharacters(CharacterMatchFunctionPtr findMatch)
{
    if (is8Bit())
        return removeCharacters(characters8(), findMatch);
    return removeCharacters(characters16(), findMatch);
}

template <typename CharType, class UCharPredicate>
inline PassRefPtr<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 data.release();
}

PassRefPtr<StringImpl> StringImpl::simplifyWhiteSpace()
{
    if (is8Bit())
        return StringImpl::simplifyMatchedCharactersToSpace<LChar>(SpaceOrNewlinePredicate());
    return StringImpl::simplifyMatchedCharactersToSpace<UChar>(SpaceOrNewlinePredicate());
}

PassRefPtr<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--) {
        LChar bc = *b++;
        if (foldCase(*a++) != foldCase(bc))
            return false;
    }
    return true;
}

bool equalIgnoringCase(const UChar* a, const LChar* b, unsigned length)
{
    while (length--) {
        LChar bc = *b++;
        if (foldCase(*a++) != foldCase(bc))
            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 kNotFound;
    size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
    RELEASE_ASSERT(matchStringLength <= numeric_limits<unsigned>::max());
    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 kNotFound;
    unsigned searchLength = length() - index;
    if (matchLength > searchLength)
        return kNotFound;
    // delta is the number of additional times to test; delta == 0 means test only once.
    unsigned delta = searchLength - matchLength;

    const UChar* searchCharacters = characters16() + index;

    // Optimization 2: keep a running hash of the strings,
    // only call equal if the hashes match.
    unsigned searchHash = 0;
    unsigned matchHash = 0;
    for (unsigned i = 0; i < matchLength; ++i) {
        searchHash += searchCharacters[i];
        matchHash += matchString[i];
    }

    unsigned i = 0;
    // keep looping until we match
    while (searchHash != matchHash || !equal(searchCharacters + i, matchString, matchLength)) {
        if (i == delta)
            return kNotFound;
        searchHash += searchCharacters[i + matchLength];
        searchHash -= searchCharacters[i];
        ++i;
    }
    return index + i;
}

template<typename CharType>
ALWAYS_INLINE size_t findIgnoringCaseInternal(const CharType* searchCharacters, const LChar* matchString, unsigned index, unsigned searchLength, unsigned matchLength)
{
    // delta is the number of additional times to test; delta == 0 means test only once.
    unsigned delta = searchLength - matchLength;

    unsigned i = 0;
    while (!equalIgnoringCase(searchCharacters + i, matchString, matchLength)) {
        if (i == delta)
            return kNotFound;
        ++i;
    }
    return index + i;
}

size_t StringImpl::findIgnoringCase(const LChar* matchString, unsigned index)
{
    // Check for null or empty string to match against
    if (!matchString)
        return kNotFound;
    size_t matchStringLength = strlen(reinterpret_cast<const char*>(matchString));
    RELEASE_ASSERT(matchStringLength <= numeric_limits<unsigned>::max());
    unsigned matchLength = matchStringLength;
    if (!matchLength)
        return min(index, length());

    // Check index & matchLength are in range.
    if (index > length())
        return kNotFound;
    unsigned searchLength = length() - index;
    if (matchLength > searchLength)
        return kNotFound;

    if (is8Bit())
        return findIgnoringCaseInternal(characters8() + index, matchString, index, searchLength, matchLength);
    return findIgnoringCaseInternal(characters16() + index, matchString, index, searchLength, matchLength);
}

template <typename SearchCharacterType, typename MatchCharacterType>
ALWAYS_INLINE static size_t findInternal(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];
    }

    unsigned i = 0;
    // keep looping until we match
    while (searchHash != matchHash || !equal(searchCharacters + i, matchCharacters, matchLength)) {
        if (i == delta)
            return kNotFound;
        searchHash += searchCharacters[i + matchLength];
        searchHash -= searchCharacters[i];
        ++i;
    }
    return index + i;
}

size_t StringImpl::find(StringImpl* matchString)
{
    // Check for null string to match against
    if (UNLIKELY(!matchString))
        return kNotFound;
    unsigned matchLength = matchString->length();

    // Optimization 1: fast case for strings of length 1.
    if (matchLength == 1) {
        if (is8Bit()) {
            if (matchString->is8Bit())
                return WTF::find(characters8(), length(), matchString->characters8()[0]);
            return WTF::find(characters8(), length(), matchString->characters16()[0]);
        }
        if (matchString->is8Bit())
            return WTF::find(characters16(), length(), matchString->characters8()[0]);
        return WTF::find(characters16(), length(), matchString->characters16()[0]);
    }

    // Check matchLength is in range.
    if (matchLength > length())
        return kNotFound;

    // Check for empty string to match against
    if (UNLIKELY(!matchLength))
        return 0;

    if (is8Bit()) {
        if (matchString->is8Bit())
            return findInternal(characters8(), matchString->characters8(), 0, length(), matchLength);
        return findInternal(characters8(), matchString->characters16(), 0, length(), matchLength);
    }

    if (matchString->is8Bit())
        return findInternal(characters16(), matchString->characters8(), 0, length(), matchLength);

    return findInternal(characters16(), matchString->characters16(), 0, length(), matchLength);
}

size_t StringImpl::find(StringImpl* matchString, unsigned index)
{
    // Check for null or empty string to match against
    if (UNLIKELY(!matchString))
        return kNotFound;

    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 min(index, length());

    // Check index & matchLength are in range.
    if (index > length())
        return kNotFound;
    unsigned searchLength = length() - index;
    if (matchLength > searchLength)
        return kNotFound;

    if (is8Bit()) {
        if (matchString->is8Bit())
            return findInternal(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
        return findInternal(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
    }

    if (matchString->is8Bit())
        return findInternal(characters16() + index, matchString->characters8(), index, searchLength, matchLength);

    return findInternal(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
}

template <typename SearchCharacterType, typename MatchCharacterType>
ALWAYS_INLINE static size_t findIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
{
    // delta is the number of additional times to test; delta == 0 means test only once.
    unsigned delta = searchLength - matchLength;

    unsigned i = 0;
    // keep looping until we match
    while (!equalIgnoringCase(searchCharacters + i, matchCharacters, matchLength)) {
        if (i == delta)
            return kNotFound;
        ++i;
    }
    return index + i;
}

size_t StringImpl::findIgnoringCase(StringImpl* matchString, unsigned index)
{
    // Check for null or empty string to match against
    if (!matchString)
        return kNotFound;
    unsigned matchLength = matchString->length();
    if (!matchLength)
        return min(index, length());

    // Check index & matchLength are in range.
    if (index > length())
        return kNotFound;
    unsigned searchLength = length() - index;
    if (matchLength > searchLength)
        return kNotFound;

    if (is8Bit()) {
        if (matchString->is8Bit())
            return findIgnoringCaseInner(characters8() + index, matchString->characters8(), index, searchLength, matchLength);
        return findIgnoringCaseInner(characters8() + index, matchString->characters16(), index, searchLength, matchLength);
    }

    if (matchString->is8Bit())
        return findIgnoringCaseInner(characters16() + index, matchString->characters8(), index, searchLength, matchLength);

    return findIgnoringCaseInner(characters16() + index, matchString->characters16(), index, searchLength, matchLength);
}

size_t StringImpl::findNextLineStart(unsigned index)
{
    if (is8Bit())
        return WTF::findNextLineStart(characters8(), m_length, index);
    return WTF::findNextLineStart(characters16(), m_length, index);
}

size_t StringImpl::count(LChar c) const
{
    int count = 0;
    if (is8Bit()) {
        for (size_t i = 0; i < m_length; ++i)
            count += characters8()[i] == c;
    } else {
        for (size_t i = 0; i < m_length; ++i)
            count += characters16()[i] == c;
    }
    return count;
}

size_t StringImpl::reverseFind(UChar c, unsigned index, unsigned stop)
{
    if (is8Bit())
        return WTF::reverseFind(characters8(), m_length, c, index, stop);
    return WTF::reverseFind(characters16(), m_length, c, index, stop);
}

template <typename SearchCharacterType, typename MatchCharacterType>
ALWAYS_INLINE static size_t reverseFindInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned stop, unsigned length, unsigned matchLength)
{
    if (stop > index || stop > length)
        return kNotFound;

    searchCharacters += stop;
    length -= stop;
    index -= stop;

    if (matchLength > length)
        return kNotFound;

    // 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 = min(index, length - matchLength);

    unsigned searchHash = 0;
    unsigned matchHash = 0;
    for (unsigned i = 0; i < matchLength; ++i) {
        searchHash += searchCharacters[delta + i];
        matchHash += matchCharacters[i];
    }

    // keep looping until we match
    while (searchHash != matchHash || !equal(searchCharacters + delta, matchCharacters, matchLength)) {
        if (!delta)
            return kNotFound;
        --delta;
        searchHash -= searchCharacters[delta + matchLength];
        searchHash += searchCharacters[delta];
    }
    return stop + delta;
}

size_t StringImpl::reverseFind(StringImpl* matchString, unsigned index, unsigned stop)
{
    // Check for null or empty string to match against
    if (!matchString)
        return kNotFound;
    unsigned matchLength = matchString->length();
    unsigned ourLength = length();
    if (!matchLength)
        return min(index, ourLength);

    // Optimization 1: fast case for strings of length 1.
    if (matchLength == 1) {
        if (is8Bit())
            return WTF::reverseFind(characters8(), ourLength, (*matchString)[0], index, stop);
        return WTF::reverseFind(characters16(), ourLength, (*matchString)[0], index, stop);
    }

    // Check index & matchLength are in range.
    if (stop + matchLength > ourLength)
        return kNotFound;

    if (is8Bit()) {
        if (matchString->is8Bit())
            return reverseFindInner(characters8(), matchString->characters8(), index, stop, ourLength, matchLength);
        return reverseFindInner(characters8(), matchString->characters16(), index, stop, ourLength, matchLength);
    }

    if (matchString->is8Bit())
        return reverseFindInner(characters16(), matchString->characters8(), index, stop, ourLength, matchLength);

    return reverseFindInner(characters16(), matchString->characters16(), index, stop, ourLength, matchLength);
}

template <typename SearchCharacterType, typename MatchCharacterType>
ALWAYS_INLINE static size_t reverseFindIgnoringCaseInner(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned length, unsigned matchLength)
{
    // delta is the number of additional times to test; delta == 0 means test only once.
    unsigned delta = min(index, length - matchLength);

    // keep looping until we match
    while (!equalIgnoringCase(searchCharacters + delta, matchCharacters, matchLength)) {
        if (!delta)
            return kNotFound;
        --delta;
    }
    return delta;
}

size_t StringImpl::reverseFindIgnoringCase(StringImpl* matchString, unsigned index)
{
    // Check for null or empty string to match against
    if (!matchString)
        return kNotFound;
    unsigned matchLength = matchString->length();
    unsigned ourLength = length();
    if (!matchLength)
        return min(index, ourLength);

    // Check index & matchLength are in range.
    if (matchLength > ourLength)
        return kNotFound;

    if (is8Bit()) {
        if (matchString->is8Bit())
            return reverseFindIgnoringCaseInner(characters8(), matchString->characters8(), index, ourLength, matchLength);
        return reverseFindIgnoringCaseInner(characters8(), matchString->characters16(), index, ourLength, matchLength);
    }

    if (matchString->is8Bit())
        return reverseFindIgnoringCaseInner(characters16(), matchString->characters8(), index, ourLength, matchLength);

    return reverseFindIgnoringCaseInner(characters16(), matchString->characters16(), index, ourLength, matchLength);
}

ALWAYS_INLINE static bool equalInner(const StringImpl* stringImpl, unsigned startOffset, const char* matchString, unsigned matchLength, bool caseSensitive)
{
    ASSERT(stringImpl);
    ASSERT(matchLength <= stringImpl->length());
    ASSERT(startOffset + matchLength <= stringImpl->length());

    if (caseSensitive) {
        if (stringImpl->is8Bit())
            return equal(stringImpl->characters8() + startOffset, reinterpret_cast<const LChar*>(matchString), matchLength);
        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);
}

bool StringImpl::startsWith(UChar character) const
{
    return m_length && (*this)[0] == character;
}

bool StringImpl::startsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
{
    ASSERT(matchLength);
    if (matchLength > length())
        return false;
    return equalInner(this, 0, matchString, matchLength, caseSensitive);
}

bool StringImpl::endsWith(StringImpl* matchString, bool caseSensitive)
{
    ASSERT(matchString);
    if (m_length >= matchString->m_length) {
        unsigned start = m_length - matchString->m_length;
        return (caseSensitive ? find(matchString, start) : findIgnoringCase(matchString, start)) == start;
    }
    return false;
}

bool StringImpl::endsWith(UChar character) const
{
    return m_length && (*this)[m_length - 1] == character;
}

bool StringImpl::endsWith(const char* matchString, unsigned matchLength, bool caseSensitive) const
{
    ASSERT(matchLength);
    if (matchLength > length())
        return false;
    unsigned startOffset = length() - matchLength;
    return equalInner(this, startOffset, matchString, matchLength, caseSensitive);
}

PassRefPtr<StringImpl> StringImpl::replace(UChar oldC, UChar newC)
{
    if (oldC == newC)
        return this;
    unsigned i;
    for (i = 0; i != m_length; ++i) {
        UChar c = is8Bit() ? characters8()[i] : characters16()[i];
        if (c == oldC)
            break;
    }
    if (i == m_length)
        return this;

    if (is8Bit()) {
        if (oldC > 0xff)
            // Looking for a 16 bit char in an 8 bit string, we're done.
            return this;

        if (newC <= 0xff) {
            LChar* data;
            LChar oldChar = static_cast<LChar>(oldC);
            LChar newChar = static_cast<LChar>(newC);

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

            for (i = 0; i != m_length; ++i) {
                LChar ch = characters8()[i];
                if (ch == oldChar)
                    ch = newChar;
                data[i] = ch;
            }
            return newImpl.release();
        }

        // There is the possibility we need to up convert from 8 to 16 bit,
        // create a 16 bit string for the result.
        UChar* data;
        RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

        for (i = 0; i != m_length; ++i) {
            UChar ch = characters8()[i];
            if (ch == oldC)
                ch = newC;
            data[i] = ch;
        }

        return newImpl.release();
    }

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

    for (i = 0; i != m_length; ++i) {
        UChar ch = characters16()[i];
        if (ch == oldC)
            ch = newC;
        data[i] = ch;
    }
    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::replace(unsigned position, unsigned lengthToReplace, StringImpl* str)
{
    position = min(position, length());
    lengthToReplace = min(lengthToReplace, length() - position);
    unsigned lengthToInsert = str ? str->length() : 0;
    if (!lengthToReplace && !lengthToInsert)
        return this;

    RELEASE_ASSERT((length() - lengthToReplace) < (numeric_limits<unsigned>::max() - lengthToInsert));

    if (is8Bit() && (!str || str->is8Bit())) {
        LChar* data;
        RefPtr<StringImpl> newImpl =
        createUninitialized(length() - lengthToReplace + lengthToInsert, data);
        memcpy(data, characters8(), position * sizeof(LChar));
        if (str)
            memcpy(data + position, str->characters8(), lengthToInsert * sizeof(LChar));
        memcpy(data + position + lengthToInsert, characters8() + position + lengthToReplace,
               (length() - position - lengthToReplace) * sizeof(LChar));
        return newImpl.release();
    }
    UChar* data;
    RefPtr<StringImpl> newImpl =
        createUninitialized(length() - lengthToReplace + lengthToInsert, data);
    if (is8Bit())
        for (unsigned i = 0; i < position; ++i)
            data[i] = characters8()[i];
    else
        memcpy(data, characters16(), position * sizeof(UChar));
    if (str) {
        if (str->is8Bit())
            for (unsigned i = 0; i < lengthToInsert; ++i)
                data[i + position] = str->characters8()[i];
        else
            memcpy(data + position, str->characters16(), lengthToInsert * sizeof(UChar));
    }
    if (is8Bit()) {
        for (unsigned i = 0; i < length() - position - lengthToReplace; ++i)
            data[i + position + lengthToInsert] = characters8()[i + position + lengthToReplace];
    } else {
        memcpy(data + position + lengthToInsert, characters16() + position + lengthToReplace,
            (length() - position - lengthToReplace) * sizeof(UChar));
    }
    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::replace(UChar pattern, StringImpl* replacement)
{
    if (!replacement)
        return this;

    if (replacement->is8Bit())
        return replace(pattern, replacement->characters8(), replacement->length());

    return replace(pattern, replacement->characters16(), replacement->length());
}

PassRefPtr<StringImpl> StringImpl::replace(UChar pattern, const LChar* replacement, unsigned repStrLength)
{
    ASSERT(replacement);

    size_t srcSegmentStart = 0;
    unsigned matchCount = 0;

    // Count the matches.
    while ((srcSegmentStart = find(pattern, srcSegmentStart)) != kNotFound) {
        ++matchCount;
        ++srcSegmentStart;
    }

    // If we have 0 matches then we don't have to do any more work.
    if (!matchCount)
        return this;

    RELEASE_ASSERT(!repStrLength || matchCount <= numeric_limits<unsigned>::max() / repStrLength);

    unsigned replaceSize = matchCount * repStrLength;
    unsigned newSize = m_length - matchCount;
    RELEASE_ASSERT(newSize < (numeric_limits<unsigned>::max() - replaceSize));

    newSize += replaceSize;

    // Construct the new data.
    size_t srcSegmentEnd;
    unsigned srcSegmentLength;
    srcSegmentStart = 0;
    unsigned dstOffset = 0;

    if (is8Bit()) {
        LChar* data;
        RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);

        while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
            srcSegmentLength = srcSegmentEnd - srcSegmentStart;
            memcpy(data + dstOffset, characters8() + srcSegmentStart, srcSegmentLength * sizeof(LChar));
            dstOffset += srcSegmentLength;
            memcpy(data + dstOffset, replacement, repStrLength * sizeof(LChar));
            dstOffset += repStrLength;
            srcSegmentStart = srcSegmentEnd + 1;
        }

        srcSegmentLength = m_length - srcSegmentStart;
        memcpy(data + dstOffset, characters8() + srcSegmentStart, srcSegmentLength * sizeof(LChar));

        ASSERT(dstOffset + srcSegmentLength == newImpl->length());

        return newImpl.release();
    }

    UChar* data;
    RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);

    while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
        srcSegmentLength = srcSegmentEnd - srcSegmentStart;
        memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));

        dstOffset += srcSegmentLength;
        for (unsigned i = 0; i < repStrLength; ++i)
            data[i + dstOffset] = replacement[i];

        dstOffset += repStrLength;
        srcSegmentStart = srcSegmentEnd + 1;
    }

    srcSegmentLength = m_length - srcSegmentStart;
    memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));

    ASSERT(dstOffset + srcSegmentLength == newImpl->length());

    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::replace(UChar pattern, const UChar* replacement, unsigned repStrLength)
{
    ASSERT(replacement);

    size_t srcSegmentStart = 0;
    unsigned matchCount = 0;

    // Count the matches.
    while ((srcSegmentStart = find(pattern, srcSegmentStart)) != kNotFound) {
        ++matchCount;
        ++srcSegmentStart;
    }

    // If we have 0 matches then we don't have to do any more work.
    if (!matchCount)
        return this;

    RELEASE_ASSERT(!repStrLength || matchCount <= numeric_limits<unsigned>::max() / repStrLength);

    unsigned replaceSize = matchCount * repStrLength;
    unsigned newSize = m_length - matchCount;
    RELEASE_ASSERT(newSize < (numeric_limits<unsigned>::max() - replaceSize));

    newSize += replaceSize;

    // Construct the new data.
    size_t srcSegmentEnd;
    unsigned srcSegmentLength;
    srcSegmentStart = 0;
    unsigned dstOffset = 0;

    if (is8Bit()) {
        UChar* data;
        RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);

        while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
            srcSegmentLength = srcSegmentEnd - srcSegmentStart;
            for (unsigned i = 0; i < srcSegmentLength; ++i)
                data[i + dstOffset] = characters8()[i + srcSegmentStart];

            dstOffset += srcSegmentLength;
            memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));

            dstOffset += repStrLength;
            srcSegmentStart = srcSegmentEnd + 1;
        }

        srcSegmentLength = m_length - srcSegmentStart;
        for (unsigned i = 0; i < srcSegmentLength; ++i)
            data[i + dstOffset] = characters8()[i + srcSegmentStart];

        ASSERT(dstOffset + srcSegmentLength == newImpl->length());

        return newImpl.release();
    }

    UChar* data;
    RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);

    while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
        srcSegmentLength = srcSegmentEnd - srcSegmentStart;
        memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));

        dstOffset += srcSegmentLength;
        memcpy(data + dstOffset, replacement, repStrLength * sizeof(UChar));

        dstOffset += repStrLength;
        srcSegmentStart = srcSegmentEnd + 1;
    }

    srcSegmentLength = m_length - srcSegmentStart;
    memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));

    ASSERT(dstOffset + srcSegmentLength == newImpl->length());

    return newImpl.release();
}

PassRefPtr<StringImpl> StringImpl::replace(StringImpl* pattern, StringImpl* replacement)
{
    if (!pattern || !replacement)
        return this;

    unsigned patternLength = pattern->length();
    if (!patternLength)
        return this;

    unsigned repStrLength = replacement->length();
    size_t srcSegmentStart = 0;
    unsigned matchCount = 0;

    // Count the matches.
    while ((srcSegmentStart = find(pattern, srcSegmentStart)) != kNotFound) {
        ++matchCount;
        srcSegmentStart += patternLength;
    }

    // If we have 0 matches, we don't have to do any more work
    if (!matchCount)
        return this;

    unsigned newSize = m_length - matchCount * patternLength;
    RELEASE_ASSERT(!repStrLength || matchCount <= numeric_limits<unsigned>::max() / repStrLength);

    RELEASE_ASSERT(newSize <= (numeric_limits<unsigned>::max() - matchCount * repStrLength));

    newSize += matchCount * repStrLength;


    // Construct the new data
    size_t srcSegmentEnd;
    unsigned srcSegmentLength;
    srcSegmentStart = 0;
    unsigned dstOffset = 0;
    bool srcIs8Bit = is8Bit();
    bool replacementIs8Bit = replacement->is8Bit();

    // There are 4 cases:
    // 1. This and replacement are both 8 bit.
    // 2. This and replacement are both 16 bit.
    // 3. This is 8 bit and replacement is 16 bit.
    // 4. This is 16 bit and replacement is 8 bit.
    if (srcIs8Bit && replacementIs8Bit) {
        // Case 1
        LChar* data;
        RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);
        while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
            srcSegmentLength = srcSegmentEnd - srcSegmentStart;
            memcpy(data + dstOffset, characters8() + srcSegmentStart, srcSegmentLength * sizeof(LChar));
            dstOffset += srcSegmentLength;
            memcpy(data + dstOffset, replacement->characters8(), repStrLength * sizeof(LChar));
            dstOffset += repStrLength;
            srcSegmentStart = srcSegmentEnd + patternLength;
        }

        srcSegmentLength = m_length - srcSegmentStart;
        memcpy(data + dstOffset, characters8() + srcSegmentStart, srcSegmentLength * sizeof(LChar));

        ASSERT(dstOffset + srcSegmentLength == newImpl->length());

        return newImpl.release();
    }

    UChar* data;
    RefPtr<StringImpl> newImpl = createUninitialized(newSize, data);
    while ((srcSegmentEnd = find(pattern, srcSegmentStart)) != kNotFound) {
        srcSegmentLength = srcSegmentEnd - srcSegmentStart;
        if (srcIs8Bit) {
            // Case 3.
            for (unsigned i = 0; i < srcSegmentLength; ++i)
                data[i + dstOffset] = characters8()[i + srcSegmentStart];
        } else {
            // Case 2 & 4.
            memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));
        }
        dstOffset += srcSegmentLength;
        if (replacementIs8Bit) {
            // Cases 2 & 3.
            for (unsigned i = 0; i < repStrLength; ++i)
                data[i + dstOffset] = replacement->characters8()[i];
        } else {
            // Case 4
            memcpy(data + dstOffset, replacement->characters16(), repStrLength * sizeof(UChar));
        }
        dstOffset += repStrLength;
        srcSegmentStart = srcSegmentEnd + patternLength;
    }

    srcSegmentLength = m_length - srcSegmentStart;
    if (srcIs8Bit) {
        // Case 3.
        for (unsigned i = 0; i < srcSegmentLength; ++i)
            data[i + dstOffset] = characters8()[i + srcSegmentStart];
    } else {
        // Cases 2 & 4.
        memcpy(data + dstOffset, characters16() + srcSegmentStart, srcSegmentLength * sizeof(UChar));
    }

    ASSERT(dstOffset + srcSegmentLength == newImpl->length());

    return newImpl.release();
}

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

template <typename CharType>
inline bool equalInternal(const StringImpl* a, const CharType* b, unsigned length)
{
    if (!a)
        return !b;
    if (!b)
        return false;

    if (a->length() != length)
        return false;
    if (a->is8Bit())
        return equal(a->characters8(), b, length);
    return equal(a->characters16(), b, length);
}

bool equal(const StringImpl* a, const LChar* b, unsigned length)
{
    return equalInternal(a, b, length);
}

bool equal(const StringImpl* a, const UChar* b, unsigned length)
{
    return equalInternal(a, b, length);
}

bool equal(const StringImpl* a, const LChar* b)
{
    if (!a)
        return !b;
    if (!b)
        return !a;

    unsigned length = a->length();

    if (a->is8Bit()) {
        const LChar* aPtr = a->characters8();
        for (unsigned i = 0; i != length; ++i) {
            LChar bc = b[i];
            LChar ac = aPtr[i];
            if (!bc)
                return false;
            if (ac != bc)
                return false;
        }

        return !b[length];
    }

    const UChar* aPtr = a->characters16();
    for (unsigned i = 0; i != length; ++i) {
        LChar bc = b[i];
        if (!bc)
            return false;
        if (aPtr[i] != bc)
            return false;
    }

    return !b[length];
}

bool equalNonNull(const StringImpl* a, const StringImpl* b)
{
    ASSERT(a && b);
    if (a == b)
        return true;

    return stringImplContentEqual(a, b);
}

bool equalIgnoringCase(const StringImpl* a, const StringImpl* b)
{
    if (a == b)
        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 && (foldCase(as[i]) == foldCase(b[i]));
        }

        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 && (foldCase(as[i]) == foldCase(b[i]));
        }
    }

    return equal && !b[length];
}

bool equalIgnoringCaseNonNull(const StringImpl* a, const StringImpl* b)
{
    ASSERT(a && b);
    if (a == b)
        return true;

    unsigned length = a->length();
    if (length != b->length())
        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);
}

bool equalIgnoringNullity(StringImpl* a, StringImpl* b)
{
    if (!a && b && !b->length())
        return true;
    if (!b && a && !a->length())
        return true;
    return equal(a, b);
}

size_t StringImpl::sizeInBytes() const
{
    size_t size = length();
    if (!is8Bit())
        size *= 2;
    return size + sizeof(*this);
}

} // namespace WTF