/*

 * 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 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/StdLibExtras.h>

#include <wtf/WTFThreadData.h>

using namespace WTF;

using namespace Unicode;

namespace WebCore {

static const unsigned minLengthToShare = 20;

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

StringImpl::~StringImpl()

{

    ASSERT(!isStatic());

    if (isAtomic())

        AtomicString::remove(this);

#if USE(JSC)

    if (isIdentifier())

        wtfThreadData().currentIdentifierTable()->remove(this);

#endif

    BufferOwnership ownership = bufferOwnership();

    if (ownership != BufferInternal) {

        if (ownership == BufferOwned) {

            ASSERT(!m_sharedBuffer);

            ASSERT(m_data);

            fastFree(const_cast<UChar*>(m_data));

        } else if (ownership == BufferSubstring) {

            ASSERT(m_substringBuffer);

            m_substringBuffer->deref();

        } else {

            ASSERT(ownership == BufferShared);

            ASSERT(m_sharedBuffer);

            m_sharedBuffer->deref();

        }

    }

}

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.

    if (length > ((std::numeric_limits<size_t>::max() - sizeof(StringImpl)) / sizeof(UChar)))

        CRASH();

    size_t size = sizeof(StringImpl) + length * sizeof(UChar);

    StringImpl* string = static_cast<StringImpl*>(fastMalloc(size));

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

    return adoptRef(new (string) StringImpl(length));

}

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

{

    if (!characters || !length)

        return empty();

    UChar* data;

    PassRefPtr<StringImpl> string = createUninitialized(length, data);

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

    return string;

}

PassRefPtr<StringImpl> StringImpl::create(const char* characters, unsigned length)

{

    if (!characters || !length)

        return empty();

    UChar* data;

    PassRefPtr<StringImpl> string = createUninitialized(length, data);

    for (unsigned i = 0; i != length; ++i) {

        unsigned char c = characters[i];

        data[i] = c;

    }

    return string;

}

PassRefPtr<StringImpl> StringImpl::create(const char* string)

{

    if (!string)

        return empty();

    return create(string, strlen(string));

}

PassRefPtr<StringImpl> StringImpl::create(const UChar* characters, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)

{

    ASSERT(characters);

    ASSERT(minLengthToShare && length >= minLengthToShare);

    return adoptRef(new StringImpl(characters, length, sharedBuffer));

}

SharedUChar* StringImpl::sharedBuffer()

{

    if (m_length < minLengthToShare)

        return 0;

    // All static strings are smaller that the minimim length to share.

    ASSERT(!isStatic());

    BufferOwnership ownership = bufferOwnership();

    if (ownership == BufferInternal)

        return 0;

    if (ownership == BufferSubstring)

        return m_substringBuffer->sharedBuffer();

    if (ownership == BufferOwned) {

        ASSERT(!m_sharedBuffer);

        m_sharedBuffer = SharedUChar::create(new SharableUChar(m_data)).releaseRef();

        m_refCountAndFlags = (m_refCountAndFlags & ~s_refCountMaskBufferOwnership) | BufferShared;

    }

    ASSERT(bufferOwnership() == BufferShared);

    ASSERT(m_sharedBuffer);

    return m_sharedBuffer;

}

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.

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

        if (!isASCIISpace(m_data[i]))

            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;

    }

    return create(m_data + start, length);

}

UChar32 StringImpl::characterStartingAt(unsigned i)

{

    if (U16_IS_SINGLE(m_data[i]))

        return m_data[i];

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

        return U16_GET_SUPPLEMENTARY(m_data[i], m_data[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:

    UChar ored = 0;

    bool noUpper = true;

    const UChar *end = m_data + m_length;

    for (const UChar* chp = m_data; 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;

    int32_t length = m_length;

    UChar* data;

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

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

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

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

            UChar c = m_data[i];

            data[i] = toASCIILower(c);

        }

        return newImpl;

    }

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

    bool error;

    int32_t realLength = Unicode::toLower(data, length, m_data, m_length, &error);

    if (!error && realLength == length)

        return newImpl;

    newImpl = createUninitialized(realLength, data);

    Unicode::toLower(data, realLength, m_data, m_length, &error);

    if (error)

        return this;

    return newImpl;

}

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.

    UChar* data;

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

    int32_t length = m_length;

    // 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 = m_data[i];

        ored |= c;

        data[i] = toASCIIUpper(c);

    }

    if (!(ored & ~0x7F))

        return newImpl;

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

    bool error;

    int32_t realLength = Unicode::toUpper(data, length, m_data, m_length, &error);

    if (!error && realLength == length)

        return newImpl;

    newImpl = createUninitialized(realLength, data);

    Unicode::toUpper(data, realLength, m_data, m_length, &error);

    if (error)

        return this;

    return newImpl;

}

PassRefPtr<StringImpl> StringImpl::secure(UChar aChar)

{

    UChar* data;

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

    int32_t length = m_length;

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

        data[i] = aChar;

    return newImpl;

}

PassRefPtr<StringImpl> StringImpl::foldCase()

{

    UChar* data;

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

    int32_t length = m_length;

    // 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 = m_data[i];

        ored |= c;

        data[i] = toASCIILower(c);

    }

    if (!(ored & ~0x7F))

        return newImpl;

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

    bool error;

    int32_t realLength = Unicode::foldCase(data, length, m_data, m_length, &error);

    if (!error && realLength == length)

        return newImpl;

    newImpl = createUninitialized(realLength, data);

    Unicode::foldCase(data, realLength, m_data, m_length, &error);

    if (error)

        return this;

    return newImpl;

}

PassRefPtr<StringImpl> StringImpl::stripWhiteSpace()

{

    if (!m_length)

        return empty();

    unsigned start = 0;

    unsigned end = m_length - 1;

    // skip white space from start

    while (start <= end && isSpaceOrNewline(m_data[start]))

        start++;

    // only white space

    if (start > end) 

        return empty();

    // skip white space from end

    while (end && isSpaceOrNewline(m_data[end]))

        end--;

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

        return this;

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

}

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

{

    const UChar* from = m_data;

    const UChar* 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 data(m_length);

    UChar* to = data.characters();

    unsigned outc = from - m_data;

    if (outc)

        memcpy(to, m_data, outc * sizeof(UChar));

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

}

PassRefPtr<StringImpl> StringImpl::simplifyWhiteSpace()

{

    StringBuffer data(m_length);

    const UChar* from = m_data;

    const UChar* fromend = from + m_length;

    int outc = 0;

    bool changedToSpace = false;

    UChar* to = data.characters();

    while (true) {

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

            if (*from != ' ')

                changedToSpace = true;

            from++;

        }

        while (from != fromend && !isSpaceOrNewline(*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);

}

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

{

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

}

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

{

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

}

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

{

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

}

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

{

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

}

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

{

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

}

int StringImpl::toInt(bool* ok)

{

    return charactersToInt(m_data, m_length, ok);

}

unsigned StringImpl::toUInt(bool* ok)

{

    return charactersToUInt(m_data, m_length, ok);

}

int64_t StringImpl::toInt64(bool* ok)

{

    return charactersToInt64(m_data, m_length, ok);

}

uint64_t StringImpl::toUInt64(bool* ok)

{

    return charactersToUInt64(m_data, m_length, ok);

}

intptr_t StringImpl::toIntPtr(bool* ok)

{

    return charactersToIntPtr(m_data, m_length, ok);

}

double StringImpl::toDouble(bool* ok)

{

    return charactersToDouble(m_data, m_length, ok);

}

float StringImpl::toFloat(bool* ok)

{

    return charactersToFloat(m_data, m_length, ok);

}

static bool equal(const UChar* a, const char* b, int length)

{

    ASSERT(length >= 0);

    while (length--) {

        unsigned char bc = *b++;

        if (*a++ != bc)

            return false;

    }

    return true;

}

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

{

    while (length--) {

        unsigned char bc = *b++;

        if (foldCase(*a++) != foldCase(bc))

            return false;

    }

    return true;

}

static inline bool equalIgnoringCase(const UChar* a, const UChar* b, int length)

{

    ASSERT(length >= 0);

    return umemcasecmp(a, b, length) == 0;

}

int codePointCompare(const StringImpl* s1, const StringImpl* s2)

{

    const unsigned l1 = s1 ? s1->length() : 0;

    const unsigned l2 = s2 ? s2->length() : 0;

    const unsigned lmin = l1 < l2 ? l1 : l2;

    const UChar* c1 = s1 ? s1->characters() : 0;

    const UChar* c2 = s2 ? s2->characters() : 0;

    unsigned pos = 0;

    while (pos < lmin && *c1 == *c2) {

        c1++;

        c2++;

        pos++;

    }

    if (pos < lmin)

        return (c1[0] > c2[0]) ? 1 : -1;

    if (l1 == l2)

        return 0;

    return (l1 > l2) ? 1 : -1;

}

int StringImpl::find(const char* chs, int index, bool caseSensitive)

{

    if (!chs || index < 0)

        return -1;

    int chsLength = strlen(chs);

    int n = m_length - index;

    if (n < 0)

        return -1;

    n -= chsLength - 1;

    if (n <= 0)

        return -1;

    const char* chsPlusOne = chs + 1;

    int chsLengthMinusOne = chsLength - 1;

    const UChar* ptr = m_data + index - 1;

    if (caseSensitive) {

        UChar c = *chs;

        do {

            if (*++ptr == c && equal(ptr + 1, chsPlusOne, chsLengthMinusOne))

                return m_length - chsLength - n + 1;

        } while (--n);

    } else {

        UChar lc = Unicode::foldCase(*chs);

        do {

            if (Unicode::foldCase(*++ptr) == lc && equalIgnoringCase(ptr + 1, chsPlusOne, chsLengthMinusOne))