ustring.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

/*
 *  Copyright (C) 1999-2000 Harri Porten ([e-mail])
 *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
 *  Copyright (C) 2007 Cameron Zwarich ([e-mail])
 *  Copyright (c) 2009, Google Inc. All rights reserved.
 *
 *  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 "UString.h"

#include "JSGlobalObjectFunctions.h"
#include "Collector.h"
#include "dtoa.h"
#include "Identifier.h"
#include "Operations.h"
#include <ctype.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <wtf/ASCIICType.h>
#include <wtf/Assertions.h>
#include <wtf/MathExtras.h>
#include <wtf/Vector.h>
#include <wtf/unicode/UTF8.h>

#if HAVE(STRING_H)
#include <string.h>
#endif
#if HAVE(STRINGS_H)
#include <strings.h>
#endif

using namespace WTF;
using namespace WTF::Unicode;
using namespace std;

// This can be tuned differently per platform by putting platform #ifs right here.
// If you don't define this macro at all, then copyChars will just call directly
// to memcpy.
#define USTRING_COPY_CHARS_INLINE_CUTOFF 20

namespace JSC {
 
extern const double NaN;
extern const double Inf;

static inline size_t overflowIndicator() { return std::numeric_limits<size_t>::max(); }
static inline size_t maxUChars() { return std::numeric_limits<size_t>::max() / sizeof(UChar); }

static inline UChar* allocChars(size_t length)
{
    ASSERT(length);
    if (length > maxUChars())
        return 0;
    return static_cast<UChar*>(tryFastMalloc(sizeof(UChar) * length));
}

static inline UChar* reallocChars(UChar* buffer, size_t length)
{
    ASSERT(length);
    if (length > maxUChars())
        return 0;
    return static_cast<UChar*>(tryFastRealloc(buffer, sizeof(UChar) * length));
}

static inline void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
{
#ifdef USTRING_COPY_CHARS_INLINE_CUTOFF
    if (numCharacters <= USTRING_COPY_CHARS_INLINE_CUTOFF) {
        for (unsigned i = 0; i < numCharacters; ++i)
            destination[i] = source[i];
        return;
    }
#endif
    memcpy(destination, source, numCharacters * sizeof(UChar));
}

COMPILE_ASSERT(sizeof(UChar) == 2, uchar_is_2_bytes)

CString::CString(const char* c)
    : m_length(strlen(c))
    , m_data(new char[m_length + 1])
{
    memcpy(m_data, c, m_length + 1);
}

CString::CString(const char* c, size_t length)
    : m_length(length)
    , m_data(new char[length + 1])
{
    memcpy(m_data, c, m_length);
    m_data[m_length] = 0;
}

CString::CString(const CString& b)
{
    m_length = b.m_length;
    if (b.m_data) {
        m_data = new char[m_length + 1];
        memcpy(m_data, b.m_data, m_length + 1);
    } else
        m_data = 0;
}

CString::~CString()
{
    delete [] m_data;
}

CString CString::adopt(char* c, size_t length)
{
    CString s;
    s.m_data = c;
    s.m_length = length;
    return s;
}

CString& CString::append(const CString& t)
{
    char* n;
    n = new char[m_length + t.m_length + 1];
    if (m_length)
        memcpy(n, m_data, m_length);
    if (t.m_length)
        memcpy(n + m_length, t.m_data, t.m_length);
    m_length += t.m_length;
    n[m_length] = 0;

    delete [] m_data;
    m_data = n;

    return *this;
}

CString& CString::operator=(const char* c)
{
    if (m_data)
        delete [] m_data;
    m_length = strlen(c);
    m_data = new char[m_length + 1];
    memcpy(m_data, c, m_length + 1);

    return *this;
}

CString& CString::operator=(const CString& str)
{
    if (this == &str)
        return *this;

    if (m_data)
        delete [] m_data;
    m_length = str.m_length;
    if (str.m_data) {
        m_data = new char[m_length + 1];
        memcpy(m_data, str.m_data, m_length + 1);
    } else
        m_data = 0;

    return *this;
}

bool operator==(const CString& c1, const CString& c2)
{
    size_t len = c1.size();
    return len == c2.size() && (len == 0 || memcmp(c1.c_str(), c2.c_str(), len) == 0);
}

// These static strings are immutable, except for rc, whose initial value is chosen to 
// reduce the possibility of it becoming zero due to ref/deref not being thread-safe.
static UChar sharedEmptyChar;
UString::BaseString* UString::Rep::nullBaseString;
UString::BaseString* UString::Rep::emptyBaseString;
UString* UString::nullUString;

static void initializeStaticBaseString(int len, UChar* buf, UString::BaseString& base)
{
    base.offset = 0;
    base.len = len;
    base.rc = INT_MAX / 2;
    base._hash = 0;
    base.m_identifierTableAndFlags.setFlag(UString::Rep::StaticFlag);
    base.m_baseString = 0;
    base.buf = buf;
    base.preCapacity = 0;
    base.usedPreCapacity = 0;
    base.capacity = 0;
    base.usedCapacity = 0;
    base.reportedCost = 0;
    base.checkConsistency();
}

void initializeUString()
{
    UString::Rep::nullBaseString = new UString::BaseString;
    initializeStaticBaseString(0, 0, *UString::Rep::nullBaseString);

    UString::Rep::emptyBaseString = new UString::BaseString;
    initializeStaticBaseString(0, &sharedEmptyChar, *UString::Rep::emptyBaseString);

    UString::nullUString = new UString;
}

static char* statBuffer = 0; // Only used for debugging via UString::ascii().

PassRefPtr<UString::Rep> UString::Rep::createCopying(const UChar* d, int l)
{
    UChar* copyD = static_cast<UChar*>(fastMalloc(l * sizeof(UChar)));
    copyChars(copyD, d, l);
    return create(copyD, l);
}

PassRefPtr<UString::Rep> UString::Rep::create(UChar* d, int l)
{
    BaseString* r = new BaseString;
    r->offset = 0;
    r->len = l;
    r->rc = 1;
    r->_hash = 0;
    r->m_baseString = 0;
    r->reportedCost = 0;
    r->buf = d;
    r->usedCapacity = l;
    r->capacity = l;
    r->usedPreCapacity = 0;
    r->preCapacity = 0;

    r->checkConsistency();

    // steal the single reference this Rep was created with
    return adoptRef(r);
}

PassRefPtr<UString::Rep> UString::Rep::create(PassRefPtr<Rep> rep, int offset, int length)
{
    ASSERT(rep);
    rep->checkConsistency();

    int repOffset = rep->offset;

    PassRefPtr<BaseString> base = rep->baseString();

    ASSERT(-(offset + repOffset) <= base->usedPreCapacity);
    ASSERT(offset + repOffset + length <= base->usedCapacity);

    Rep* r = new Rep;
    r->offset = repOffset + offset;
    r->len = length;
    r->rc = 1;
    r->_hash = 0;
    r->setBaseString(base);

    r->checkConsistency();

    // steal the single reference this Rep was created with
    return adoptRef(r);
}

PassRefPtr<UString::Rep> UString::Rep::createFromUTF8(const char* string)
{
    if (!string)
        return &UString::Rep::null();

    size_t length = strlen(string);
    Vector<UChar, 1024> buffer(length);
    UChar* p = buffer.data();
    if (conversionOK != convertUTF8ToUTF16(&string, string + length, &p, p + length))
        return &UString::Rep::null();

    return UString::Rep::createCopying(buffer.data(), p - buffer.data());
}

void UString::Rep::destroy()
{
    checkConsistency();

    // Static null and empty strings can never be destroyed, but we cannot rely on 
    // reference counting, because ref/deref are not thread-safe.
    if (!isStatic()) {
        if (identifierTable())
            Identifier::remove(this);
        UString::BaseString* base = baseString();
        if (base == this)
            fastFree(base->buf);
        else
            base->deref();

        delete this;
    }
}

// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
// or anything like that.
const unsigned PHI = 0x9e3779b9U;

// Paul Hsieh's SuperFastHash
// http://www.azillionmonkeys.com/qed/hash.html
unsigned UString::Rep::computeHash(const UChar* s, int len)
{
    unsigned l = len;
    uint32_t hash = PHI;
    uint32_t tmp;

    int rem = l & 1;
    l >>= 1;

    // Main loop
    for (; l > 0; l--) {
        hash += s[0];
        tmp = (s[1] << 11) ^ hash;
        hash = (hash << 16) ^ tmp;
        s += 2;
        hash += hash >> 11;
    }

    // Handle end case
    if (rem) {
        hash += s[0];
        hash ^= hash << 11;
        hash += hash >> 17;
    }

    // Force "avalanching" of final 127 bits
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 2;
    hash += hash >> 15;
    hash ^= hash << 10;

    // this avoids ever returning a hash code of 0, since that is used to
    // signal "hash not computed yet", using a value that is likely to be
    // effectively the same as 0 when the low bits are masked
    if (hash == 0)
        hash = 0x80000000;

    return hash;
}

// Paul Hsieh's SuperFastHash
// http://www.azillionmonkeys.com/qed/hash.html
unsigned UString::Rep::computeHash(const char* s, int l)
{
    // This hash is designed to work on 16-bit chunks at a time. But since the normal case
    // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
    // were 16-bit chunks, which should give matching results

    uint32_t hash = PHI;
    uint32_t tmp;

    size_t rem = l & 1;
    l >>= 1;

    // Main loop
    for (; l > 0; l--) {
        hash += static_cast<unsigned char>(s[0]);
        tmp = (static_cast<unsigned char>(s[1]) << 11) ^ hash;
        hash = (hash << 16) ^ tmp;
        s += 2;
        hash += hash >> 11;
    }

    // Handle end case
    if (rem) {
        hash += static_cast<unsigned char>(s[0]);
        hash ^= hash << 11;
        hash += hash >> 17;
    }

    // Force "avalanching" of final 127 bits
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 2;
    hash += hash >> 15;
    hash ^= hash << 10;

    // this avoids ever returning a hash code of 0, since that is used to
    // signal "hash not computed yet", using a value that is likely to be
    // effectively the same as 0 when the low bits are masked
    if (hash == 0)
        hash = 0x80000000;

    return hash;
}

#ifndef NDEBUG
void UString::Rep::checkConsistency() const
{
    const UString::BaseString* base = baseString();

    // There is no recursion for base strings.
    ASSERT(base == base->baseString());

    if (isStatic()) {
        // There are only two static strings: null and empty.
        ASSERT(!len);

        // Static strings cannot get in identifier tables, because they are globally shared.
        ASSERT(!identifierTable());
    }

    // The string fits in buffer.
    ASSERT(base->usedPreCapacity <= base->preCapacity);
    ASSERT(base->usedCapacity <= base->capacity);
    ASSERT(-offset <= base->usedPreCapacity);
    ASSERT(offset + len <= base->usedCapacity);
}
#endif

// put these early so they can be inlined
static inline size_t expandedSize(size_t size, size_t otherSize)
{
    // Do the size calculation in two parts, returning overflowIndicator if
    // we overflow the maximum value that we can handle.

    if (size > maxUChars())
        return overflowIndicator();

    size_t expandedSize = ((size + 10) / 10 * 11) + 1;
    if (maxUChars() - expandedSize < otherSize)
        return overflowIndicator();

    return expandedSize + otherSize;
}

static inline bool expandCapacity(UString::Rep* rep, int requiredLength)
{
    rep->checkConsistency();

    UString::BaseString* base = rep->baseString();

    if (requiredLength > base->capacity) {
        size_t newCapacity = expandedSize(requiredLength, base->preCapacity);
        UChar* oldBuf = base->buf;
        base->buf = reallocChars(base->buf, newCapacity);
        if (!base->buf) {
            base->buf = oldBuf;
            return false;
        }
        base->capacity = newCapacity - base->preCapacity;
    }
    if (requiredLength > base->usedCapacity)
        base->usedCapacity = requiredLength;

    rep->checkConsistency();
    return true;
}

void UString::expandCapacity(int requiredLength)
{
    if (!JSC::expandCapacity(m_rep.get(), requiredLength))
        makeNull();
}

void UString::expandPreCapacity(int requiredPreCap)
{
    m_rep->checkConsistency();

    BaseString* base = m_rep->baseString();

    if (requiredPreCap > base->preCapacity) {
        size_t newCapacity = expandedSize(requiredPreCap, base->capacity);
        int delta = newCapacity - base->capacity - base->preCapacity;

        UChar* newBuf = allocChars(newCapacity);
        if (!newBuf) {
            makeNull();
            return;
        }
        copyChars(newBuf + delta, base->buf, base->capacity + base->preCapacity);
        fastFree(base->buf);
        base->buf = newBuf;

        base->preCapacity = newCapacity - base->capacity;
    }
    if (requiredPreCap > base->usedPreCapacity)
        base->usedPreCapacity = requiredPreCap;

    m_rep->checkConsistency();
}

static PassRefPtr<UString::Rep> createRep(const char* c)
{
    if (!c)
        return &UString::Rep::null();

    if (!c[0])
        return &UString::Rep::empty();

    size_t length = strlen(c);
    UChar* d = allocChars(length);
    if (!d)
        return &UString::Rep::null();
    else {
        for (size_t i = 0; i < length; i++)
            d[i] = static_cast<unsigned char>(c[i]); // use unsigned char to zero-extend instead of sign-extend
        return UString::Rep::create(d, static_cast<int>(length));
    }

}

UString::UString(const char* c)
    : m_rep(createRep(c))
{
}

UString::UString(const UChar* c, int length)
{
    if (length == 0) 
        m_rep = &Rep::empty();
    else
        m_rep = Rep::createCopying(c, length);
}

UString::UString(UChar* c, int length, bool copy)
{
    if (length == 0)
        m_rep = &Rep::empty();
    else if (copy)
        m_rep = Rep::createCopying(c, length);
    else
        m_rep = Rep::create(c, length);
}

UString::UString(const Vector<UChar>& buffer)
{
    if (!buffer.size())
        m_rep = &Rep::empty();
    else
        m_rep = Rep::createCopying(buffer.data(), buffer.size());
}

static ALWAYS_INLINE PassRefPtr<UString::Rep> concatenate(PassRefPtr<UString::Rep> r, const UChar* tData, int tSize)
{
    RefPtr<UString::Rep> rep = r;