#ifndef StringImpl_h
#define StringImpl_h
#include <limits.h>
#include "wtf/ASCIICType.h"
#include "wtf/Forward.h"
#include "wtf/HashMap.h"
#include "wtf/StringHasher.h"
#include "wtf/Vector.h"
#include "wtf/WTFExport.h"
#include "wtf/unicode/Unicode.h"
#if USE(CF)
typedef const struct __CFString * CFStringRef;
#endif
#ifdef __OBJC__
@class NSString;
#endif
namespace WTF {
struct AlreadyHashed;
struct CStringTranslator;
template<typename CharacterType> struct HashAndCharactersTranslator;
struct HashAndUTF8CharactersTranslator;
struct LCharBufferTranslator;
struct CharBufferFromLiteralDataTranslator;
struct SubstringTranslator;
struct UCharBufferTranslator;
template<typename> class RetainPtr;
enum TextCaseSensitivity { TextCaseSensitive, TextCaseInsensitive };
enum StripBehavior { StripExtraWhiteSpace, DoNotStripWhiteSpace };
typedef bool (*CharacterMatchFunctionPtr)(UChar);
typedef bool (*IsWhiteSpaceFunctionPtr)(UChar);
typedef HashMap<unsigned, StringImpl*, AlreadyHashed> StaticStringsTable;
#undef STRING_STATS
#ifdef STRING_STATS
struct StringStats {
inline void add8BitString(unsigned length)
{
++m_totalNumberStrings;
++m_number8BitStrings;
m_total8BitData += length;
}
inline void add16BitString(unsigned length)
{
++m_totalNumberStrings;
++m_number16BitStrings;
m_total16BitData += length;
}
void removeString(StringImpl*);
void printStats();
static const unsigned s_printStringStatsFrequency = 5000;
static unsigned s_stringRemovesTillPrintStats;
unsigned m_totalNumberStrings;
unsigned m_number8BitStrings;
unsigned m_number16BitStrings;
unsigned long long m_total8BitData;
unsigned long long m_total16BitData;
};
void addStringForStats(StringImpl*);
void removeStringForStats(StringImpl*);
#define STRING_STATS_ADD_8BIT_STRING(length) StringImpl::stringStats().add8BitString(length); addStringForStats(this)
#define STRING_STATS_ADD_16BIT_STRING(length) StringImpl::stringStats().add16BitString(length); addStringForStats(this)
#define STRING_STATS_REMOVE_STRING(string) StringImpl::stringStats().removeString(string); removeStringForStats(this)
#else
#define STRING_STATS_ADD_8BIT_STRING(length) ((void)0)
#define STRING_STATS_ADD_16BIT_STRING(length) ((void)0)
#define STRING_STATS_REMOVE_STRING(string) ((void)0)
#endif
class WTF_EXPORT StringImpl {
WTF_MAKE_NONCOPYABLE(StringImpl);
friend struct WTF::CStringTranslator;
template<typename CharacterType> friend struct WTF::HashAndCharactersTranslator;
friend struct WTF::HashAndUTF8CharactersTranslator;
friend struct WTF::CharBufferFromLiteralDataTranslator;
friend struct WTF::LCharBufferTranslator;
friend struct WTF::SubstringTranslator;
friend struct WTF::UCharBufferTranslator;
private:
void* operator new(size_t);
void* operator new(size_t, void* ptr) { return ptr; };
void operator delete(void*);
enum ConstructEmptyStringTag { ConstructEmptyString };
explicit StringImpl(ConstructEmptyStringTag)
: m_refCount(1)
, m_length(0)
, m_hash(0)
, m_isAtomic(false)
, m_is8Bit(true)
, m_isStatic(true)
{
STRING_STATS_ADD_8BIT_STRING(m_length);
hash();
}
enum Force8Bit { Force8BitConstructor };
StringImpl(unsigned length, Force8Bit)
: m_refCount(1)
, m_length(length)
, m_hash(0)
, m_isAtomic(false)
, m_is8Bit(true)
, m_isStatic(false)
{
ASSERT(m_length);
STRING_STATS_ADD_8BIT_STRING(m_length);
}
StringImpl(unsigned length)
: m_refCount(1)
, m_length(length)
, m_hash(0)
, m_isAtomic(false)
, m_is8Bit(false)
, m_isStatic(false)
{
ASSERT(m_length);
STRING_STATS_ADD_16BIT_STRING(m_length);
}
enum StaticStringTag { StaticString };
StringImpl(unsigned length, unsigned hash, StaticStringTag)
: m_refCount(1)
, m_length(length)
, m_hash(hash)
, m_isAtomic(false)
, m_is8Bit(true)
, m_isStatic(true)
{
}
public:
~StringImpl();
static StringImpl* createStatic(const char* string, unsigned length, unsigned hash);
static void freezeStaticStrings();
static const StaticStringsTable& allStaticStrings();
static unsigned highestStaticStringLength() { return m_highestStaticStringLength; }
static PassRefPtr<StringImpl> create(const UChar*, unsigned length);
static PassRefPtr<StringImpl> create(const LChar*, unsigned length);
static PassRefPtr<StringImpl> create8BitIfPossible(const UChar*, unsigned length);
template<size_t inlineCapacity>
static PassRefPtr<StringImpl> create8BitIfPossible(const Vector<UChar, inlineCapacity>& vector)
{
return create8BitIfPossible(vector.data(), vector.size());
}
ALWAYS_INLINE static PassRefPtr<StringImpl> create(const char* s, unsigned length) { return create(reinterpret_cast<const LChar*>(s), length); }
static PassRefPtr<StringImpl> create(const LChar*);
ALWAYS_INLINE static PassRefPtr<StringImpl> create(const char* s) { return create(reinterpret_cast<const LChar*>(s)); }
static PassRefPtr<StringImpl> createUninitialized(unsigned length, LChar*& data);
static PassRefPtr<StringImpl> createUninitialized(unsigned length, UChar*& data);
static PassRefPtr<StringImpl> reallocate(PassRefPtr<StringImpl> originalString, unsigned length);
void truncateAssumingIsolated(unsigned length)
{
ASSERT(hasOneRef());
ASSERT(length <= m_length);
m_length = length;
}
unsigned length() const { return m_length; }
bool is8Bit() const { return m_is8Bit; }
ALWAYS_INLINE const LChar* characters8() const { ASSERT(is8Bit()); return reinterpret_cast<const LChar*>(this + 1); }
ALWAYS_INLINE const UChar* characters16() const { ASSERT(!is8Bit()); return reinterpret_cast<const UChar*>(this + 1); }
template <typename CharType>
ALWAYS_INLINE const CharType * getCharacters() const;
size_t sizeInBytes() const;
bool isAtomic() const { return m_isAtomic; }
void setIsAtomic(bool isAtomic) { m_isAtomic = isAtomic; }
bool isStatic() const { return m_isStatic; }
private:
void setHash(unsigned hash) const
{
ASSERT(!hasHash());
ASSERT(hash == (is8Bit() ? StringHasher::computeHashAndMaskTop8Bits(characters8(), m_length) : StringHasher::computeHashAndMaskTop8Bits(characters16(), m_length)));
m_hash = hash;
ASSERT(hash);
}
unsigned rawHash() const
{
return m_hash;
}
void destroyIfNotStatic();
public:
bool hasHash() const
{
return rawHash() != 0;
}
unsigned existingHash() const
{
ASSERT(hasHash());
return rawHash();
}
unsigned hash() const
{
if (hasHash())
return existingHash();
return hashSlowCase();
}
ALWAYS_INLINE bool hasOneRef() const
{
return m_refCount == 1;
}
ALWAYS_INLINE void ref()
{
++m_refCount;
}
ALWAYS_INLINE void deref()
{
if (hasOneRef()) {
destroyIfNotStatic();
return;
}
--m_refCount;
}
static StringImpl* empty();
template <typename T> static void copyChars(T* destination, const T* source, unsigned numCharacters)
{
memcpy(destination, source, numCharacters * sizeof(T));
}
ALWAYS_INLINE static void copyChars(UChar* destination, const LChar* source, unsigned numCharacters)
{
for (unsigned i = 0; i < numCharacters; ++i)
destination[i] = source[i];
}
PassRefPtr<StringImpl> isolatedCopy() const;
PassRefPtr<StringImpl> substring(unsigned pos, unsigned len = UINT_MAX);
UChar operator[](unsigned i) const
{
ASSERT_WITH_SECURITY_IMPLICATION(i < m_length);
if (is8Bit())
return characters8()[i];
return characters16()[i];
}
UChar32 characterStartingAt(unsigned);
bool containsOnlyWhitespace();
int toIntStrict(bool* ok = 0, int base = 10);
unsigned toUIntStrict(bool* ok = 0, int base = 10);
int64_t toInt64Strict(bool* ok = 0, int base = 10);
uint64_t toUInt64Strict(bool* ok = 0, int base = 10);
intptr_t toIntPtrStrict(bool* ok = 0, int base = 10);
int toInt(bool* ok = 0);
unsigned toUInt(bool* ok = 0);
int64_t toInt64(bool* ok = 0);
uint64_t toUInt64(bool* ok = 0);
intptr_t toIntPtr(bool* ok = 0);
double toDouble(bool* ok = 0);
float toFloat(bool* ok = 0);
PassRefPtr<StringImpl> lower();
PassRefPtr<StringImpl> upper();
PassRefPtr<StringImpl> lower(const AtomicString& localeIdentifier);
PassRefPtr<StringImpl> upper(const AtomicString& localeIdentifier);
PassRefPtr<StringImpl> fill(UChar);
PassRefPtr<StringImpl> foldCase();
PassRefPtr<StringImpl> stripWhiteSpace();
PassRefPtr<StringImpl> stripWhiteSpace(IsWhiteSpaceFunctionPtr);
PassRefPtr<StringImpl> simplifyWhiteSpace(StripBehavior stripBehavior = StripExtraWhiteSpace);
PassRefPtr<StringImpl> simplifyWhiteSpace(IsWhiteSpaceFunctionPtr, StripBehavior stripBehavior = StripExtraWhiteSpace);
PassRefPtr<StringImpl> removeCharacters(CharacterMatchFunctionPtr);
template <typename CharType>
ALWAYS_INLINE PassRefPtr<StringImpl> removeCharacters(const CharType* characters, CharacterMatchFunctionPtr);
size_t find(LChar character, unsigned start = 0);
size_t find(char character, unsigned start = 0);
size_t find(UChar character, unsigned start = 0);
size_t find(CharacterMatchFunctionPtr, unsigned index = 0);
size_t find(const LChar*, unsigned index = 0);
ALWAYS_INLINE size_t find(const char* s, unsigned index = 0) { return find(reinterpret_cast<const LChar*>(s), index); }
size_t find(StringImpl*);
size_t find(StringImpl*, unsigned index);
size_t findIgnoringCase(const LChar*, unsigned index = 0);
ALWAYS_INLINE size_t findIgnoringCase(const char* s, unsigned index = 0) { return findIgnoringCase(reinterpret_cast<const LChar*>(s), index); }
size_t findIgnoringCase(StringImpl*, unsigned index = 0);
size_t findNextLineStart(unsigned index = UINT_MAX);
size_t reverseFind(UChar, unsigned index = UINT_MAX);
size_t reverseFind(StringImpl*, unsigned index = UINT_MAX);
size_t reverseFindIgnoringCase(StringImpl*, unsigned index = UINT_MAX);
size_t count(LChar) const;
bool startsWith(StringImpl* str, bool caseSensitive = true) { return (caseSensitive ? reverseFind(str, 0) : reverseFindIgnoringCase(str, 0)) == 0; }
bool startsWith(UChar) const;
bool startsWith(const char*, unsigned matchLength, bool caseSensitive) const;
template<unsigned matchLength>
bool startsWith(const char (&prefix)[matchLength], bool caseSensitive = true) const { return startsWith(prefix, matchLength - 1, caseSensitive); }
bool endsWith(StringImpl*, bool caseSensitive = true);
bool endsWith(UChar) const;
bool endsWith(const char*, unsigned matchLength, bool caseSensitive) const;
template<unsigned matchLength>
bool endsWith(const char (&prefix)[matchLength], bool caseSensitive = true) const { return endsWith(prefix, matchLength - 1, caseSensitive); }
PassRefPtr<StringImpl> replace(UChar, UChar);
PassRefPtr<StringImpl> replace(UChar, StringImpl*);
ALWAYS_INLINE PassRefPtr<StringImpl> replace(UChar pattern, const char* replacement, unsigned replacementLength) { return replace(pattern, reinterpret_cast<const LChar*>(replacement), replacementLength); }
PassRefPtr<StringImpl> replace(UChar, const LChar*, unsigned replacementLength);
PassRefPtr<StringImpl> replace(UChar, const UChar*, unsigned replacementLength);
PassRefPtr<StringImpl> replace(StringImpl*, StringImpl*);
PassRefPtr<StringImpl> replace(unsigned index, unsigned len, StringImpl*);
PassRefPtr<StringImpl> upconvertedString();
#if USE(CF)
RetainPtr<CFStringRef> createCFString();
#endif
#ifdef __OBJC__
operator NSString*();
#endif
#ifdef STRING_STATS
ALWAYS_INLINE static StringStats& stringStats() { return m_stringStats; }
#endif
private:
template<typename CharType> static size_t allocationSize(unsigned length)
{
RELEASE_ASSERT(length <= ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharType)));
return sizeof(StringImpl) + length * sizeof(CharType);
}
template <class UCharPredicate> PassRefPtr<StringImpl> stripMatchedCharacters(UCharPredicate);
template <typename CharType, class UCharPredicate> PassRefPtr<StringImpl> simplifyMatchedCharactersToSpace(UCharPredicate, StripBehavior);
NEVER_INLINE unsigned hashSlowCase() const;
#ifdef STRING_STATS
static StringStats m_stringStats;
#endif
static unsigned m_highestStaticStringLength;
#ifndef NDEBUG
void assertHashIsCorrect()
{
ASSERT(hasHash());
ASSERT(existingHash() == StringHasher::computeHashAndMaskTop8Bits(characters8(), length()));
}
#endif
private:
unsigned m_refCount;
unsigned m_length;
mutable unsigned m_hash : 24;
unsigned m_isAtomic : 1;
unsigned m_is8Bit : 1;
unsigned m_isStatic : 1;
};
template <>
ALWAYS_INLINE const LChar* StringImpl::getCharacters<LChar>() const { return characters8(); }
template <>
ALWAYS_INLINE const UChar* StringImpl::getCharacters<UChar>() const { return characters16(); }
WTF_EXPORT bool equal(const StringImpl*, const StringImpl*);
WTF_EXPORT bool equal(const StringImpl*, const LChar*);
inline bool equal(const StringImpl* a, const char* b) { return equal(a, reinterpret_cast<const LChar*>(b)); }
WTF_EXPORT bool equal(const StringImpl*, const LChar*, unsigned);
WTF_EXPORT bool equal(const StringImpl*, const UChar*, unsigned);
inline bool equal(const StringImpl* a, const char* b, unsigned length) { return equal(a, reinterpret_cast<const LChar*>(b), length); }
inline bool equal(const LChar* a, StringImpl* b) { return equal(b, a); }
inline bool equal(const char* a, StringImpl* b) { return equal(b, reinterpret_cast<const LChar*>(a)); }
WTF_EXPORT bool equalNonNull(const StringImpl* a, const StringImpl* b);
template<typename CharType>
ALWAYS_INLINE bool equal(const CharType* a, const CharType* b, unsigned length) { return !memcmp(a, b, length * sizeof(CharType)); }
ALWAYS_INLINE bool equal(const LChar* a, const UChar* b, unsigned length)
{
for (unsigned i = 0; i < length; ++i) {
if (a[i] != b[i])
return false;
}
return true;
}
ALWAYS_INLINE bool equal(const UChar* a, const LChar* b, unsigned length) { return equal(b, a, length); }
WTF_EXPORT bool equalIgnoringCase(const StringImpl*, const StringImpl*);
WTF_EXPORT bool equalIgnoringCase(const StringImpl*, const LChar*);
inline bool equalIgnoringCase(const LChar* a, const StringImpl* b) { return equalIgnoringCase(b, a); }
WTF_EXPORT bool equalIgnoringCase(const LChar*, const LChar*, unsigned);
WTF_EXPORT bool equalIgnoringCase(const UChar*, const LChar*, unsigned);
inline bool equalIgnoringCase(const UChar* a, const char* b, unsigned length) { return equalIgnoringCase(a, reinterpret_cast<const LChar*>(b), length); }
inline bool equalIgnoringCase(const LChar* a, const UChar* b, unsigned length) { return equalIgnoringCase(b, a, length); }
inline bool equalIgnoringCase(const char* a, const UChar* b, unsigned length) { return equalIgnoringCase(b, reinterpret_cast<const LChar*>(a), length); }
inline bool equalIgnoringCase(const char* a, const LChar* b, unsigned length) { return equalIgnoringCase(b, reinterpret_cast<const LChar*>(a), length); }
inline bool equalIgnoringCase(const UChar* a, const UChar* b, int length)
{
ASSERT(length >= 0);
return !Unicode::umemcasecmp(a, b, length);
}
WTF_EXPORT bool equalIgnoringCaseNonNull(const StringImpl*, const StringImpl*);
WTF_EXPORT bool equalIgnoringNullity(StringImpl*, StringImpl*);
template<typename CharacterType>
inline size_t find(const CharacterType* characters, unsigned length, CharacterType matchCharacter, unsigned index = 0)
{
while (index < length) {
if (characters[index] == matchCharacter)
return index;
++index;
}
return kNotFound;
}
ALWAYS_INLINE size_t find(const UChar* characters, unsigned length, LChar matchCharacter, unsigned index = 0)
{
return find(characters, length, static_cast<UChar>(matchCharacter), index);
}
inline size_t find(const LChar* characters, unsigned length, UChar matchCharacter, unsigned index = 0)
{
if (matchCharacter & ~0xFF)
return kNotFound;
return find(characters, length, static_cast<LChar>(matchCharacter), index);
}
inline size_t find(const LChar* characters, unsigned length, CharacterMatchFunctionPtr matchFunction, unsigned index = 0)
{
while (index < length) {
if (matchFunction(characters[index]))
return index;
++index;
}
return kNotFound;
}
inline size_t find(const UChar* characters, unsigned length, CharacterMatchFunctionPtr matchFunction, unsigned index = 0)
{
while (index < length) {
if (matchFunction(characters[index]))
return index;
++index;
}
return kNotFound;
}
template<typename CharacterType>
inline size_t findNextLineStart(const CharacterType* characters, unsigned length, unsigned index = 0)
{
while (index < length) {
CharacterType c = characters[index++];
if ((c != '\n') && (c != '\r'))
continue;
if (index < length) {
if (c == '\n')
return index;
CharacterType c2 = characters[index];
if (c2 != '\n')
return index;
if (++index < length)
return index;
}
}
return kNotFound;
}
template<typename CharacterType>
inline size_t reverseFindLineTerminator(const CharacterType* characters, unsigned length, unsigned index = UINT_MAX)
{
if (!length)
return kNotFound;
if (index >= length)
index = length - 1;
CharacterType c = characters[index];
while ((c != '\n') && (c != '\r')) {
if (!index--)
return kNotFound;
c = characters[index];
}
return index;
}
template<typename CharacterType>
inline size_t reverseFind(const CharacterType* characters, unsigned length, CharacterType matchCharacter, unsigned index = UINT_MAX)
{
if (!length)
return kNotFound;
if (index >= length)
index = length - 1;
while (characters[index] != matchCharacter) {
if (!index--)
return kNotFound;
}
return index;
}
ALWAYS_INLINE size_t reverseFind(const UChar* characters, unsigned length, LChar matchCharacter, unsigned index = UINT_MAX)
{
return reverseFind(characters, length, static_cast<UChar>(matchCharacter), index);
}
inline size_t reverseFind(const LChar* characters, unsigned length, UChar matchCharacter, unsigned index = UINT_MAX)
{
if (matchCharacter & ~0xFF)
return kNotFound;
return reverseFind(characters, length, static_cast<LChar>(matchCharacter), index);
}
inline size_t StringImpl::find(LChar character, unsigned start)
{
if (is8Bit())
return WTF::find(characters8(), m_length, character, start);
return WTF::find(characters16(), m_length, character, start);
}
ALWAYS_INLINE size_t StringImpl::find(char character, unsigned start)
{
return find(static_cast<LChar>(character), start);
}
inline size_t StringImpl::find(UChar character, unsigned start)
{
if (is8Bit())
return WTF::find(characters8(), m_length, character, start);
return WTF::find(characters16(), m_length, character, start);
}
inline unsigned lengthOfNullTerminatedString(const UChar* string)
{
size_t length = 0;
while (string[length] != UChar(0))
++length;
RELEASE_ASSERT(length <= std::numeric_limits<unsigned>::max());
return static_cast<unsigned>(length);
}
template<size_t inlineCapacity>
bool equalIgnoringNullity(const Vector<UChar, inlineCapacity>& a, StringImpl* b)
{
if (!b)
return !a.size();
if (a.size() != b->length())
return false;
if (b->is8Bit())
return equal(a.data(), b->characters8(), b->length());
return equal(a.data(), b->characters16(), b->length());
}
template<typename CharacterType1, typename CharacterType2>
static inline int codePointCompare(unsigned l1, unsigned l2, const CharacterType1* c1, const CharacterType2* c2)
{
const unsigned lmin = l1 < l2 ? l1 : l2;
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;
}
static inline int codePointCompare8(const StringImpl* string1, const StringImpl* string2)
{
return codePointCompare(string1->length(), string2->length(), string1->characters8(), string2->characters8());
}
static inline int codePointCompare16(const StringImpl* string1, const StringImpl* string2)
{
return codePointCompare(string1->length(), string2->length(), string1->characters16(), string2->characters16());
}
static inline int codePointCompare8To16(const StringImpl* string1, const StringImpl* string2)
{
return codePointCompare(string1->length(), string2->length(), string1->characters8(), string2->characters16());
}
static inline int codePointCompare(const StringImpl* string1, const StringImpl* string2)
{
if (!string1)
return (string2 && string2->length()) ? -1 : 0;
if (!string2)
return string1->length() ? 1 : 0;
bool string1Is8Bit = string1->is8Bit();
bool string2Is8Bit = string2->is8Bit();
if (string1Is8Bit) {
if (string2Is8Bit)
return codePointCompare8(string1, string2);
return codePointCompare8To16(string1, string2);
}
if (string2Is8Bit)
return -codePointCompare8To16(string2, string1);
return codePointCompare16(string1, string2);
}
static inline bool isSpaceOrNewline(UChar c)
{
return c <= 0x7F ? WTF::isASCIISpace(c) : WTF::Unicode::direction(c) == WTF::Unicode::WhiteSpaceNeutral;
}
inline PassRefPtr<StringImpl> StringImpl::isolatedCopy() const
{
if (is8Bit())
return create(characters8(), m_length);
return create(characters16(), m_length);
}
struct StringHash;
template<typename T> struct DefaultHash;
template<> struct DefaultHash<StringImpl*> {
typedef StringHash Hash;
};
template<> struct DefaultHash<RefPtr<StringImpl> > {
typedef StringHash Hash;
};
}
using WTF::StringImpl;
using WTF::equal;
using WTF::equalNonNull;
using WTF::TextCaseSensitivity;
using WTF::TextCaseSensitive;
using WTF::TextCaseInsensitive;
#endif