blob: 87a64eeab25aa74dc0b91907b2c8448b95d1fc9c [file] [log] [blame]
/*
* Copyright (C) 2004-2008, 2013-2014 Apple Inc. All rights reserved.
* Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
* Copyright (C) 2012 Google Inc. All rights reserved.
* Copyright (C) 2015 Yusuke Suzuki<utatane.tea@gmail.com>. 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 <wtf/text/AtomStringImpl.h>
#include <wtf/CommaPrinter.h>
#include <wtf/DataLog.h>
#include <wtf/HashSet.h>
#include <wtf/StringPrintStream.h>
#include <wtf/Threading.h>
#include <wtf/text/AtomStringTable.h>
#include <wtf/text/IntegerToStringConversion.h>
#include <wtf/text/StringHash.h>
#include <wtf/unicode/UTF8Conversion.h>
#if USE(WEB_THREAD)
#include <wtf/Lock.h>
#endif
namespace WTF {
using namespace Unicode;
#if USE(WEB_THREAD)
class AtomStringTableLocker : public LockHolder {
WTF_MAKE_NONCOPYABLE(AtomStringTableLocker);
static Lock s_stringTableLock;
public:
AtomStringTableLocker()
: LockHolder(&s_stringTableLock)
{
}
};
Lock AtomStringTableLocker::s_stringTableLock;
#else
class AtomStringTableLocker {
WTF_MAKE_NONCOPYABLE(AtomStringTableLocker);
public:
AtomStringTableLocker() { }
};
#endif // USE(WEB_THREAD)
using StringTableImpl = HashSet<StringImpl*>;
static ALWAYS_INLINE StringTableImpl& stringTable()
{
return Thread::current().atomStringTable()->table();
}
template<typename T, typename HashTranslator>
static inline Ref<AtomStringImpl> addToStringTable(AtomStringTableLocker&, StringTableImpl& atomStringTable, const T& value)
{
auto addResult = atomStringTable.add<HashTranslator>(value);
// If the string is newly-translated, then we need to adopt it.
// The boolean in the pair tells us if that is so.
if (addResult.isNewEntry)
return adoptRef(static_cast<AtomStringImpl&>(**addResult.iterator));
return *static_cast<AtomStringImpl*>(*addResult.iterator);
}
template<typename T, typename HashTranslator>
static inline Ref<AtomStringImpl> addToStringTable(const T& value)
{
AtomStringTableLocker locker;
return addToStringTable<T, HashTranslator>(locker, stringTable(), value);
}
struct CStringTranslator {
static unsigned hash(const LChar* characters)
{
return StringHasher::computeHashAndMaskTop8Bits(characters);
}
static inline bool equal(StringImpl* str, const LChar* characters)
{
return WTF::equal(str, characters);
}
static void translate(StringImpl*& location, const LChar* const& characters, unsigned hash)
{
location = &StringImpl::create(characters).leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
RefPtr<AtomStringImpl> AtomStringImpl::add(const LChar* characters)
{
if (!characters)
return nullptr;
if (!*characters)
return static_cast<AtomStringImpl*>(StringImpl::empty());
return addToStringTable<const LChar*, CStringTranslator>(characters);
}
template<typename CharacterType>
struct HashTranslatorCharBuffer {
const CharacterType* characters;
unsigned length;
unsigned hash;
HashTranslatorCharBuffer(const CharacterType* characters, unsigned length)
: characters(characters)
, length(length)
, hash(StringHasher::computeHashAndMaskTop8Bits(characters, length))
{
}
HashTranslatorCharBuffer(const CharacterType* characters, unsigned length, unsigned hash)
: characters(characters)
, length(length)
, hash(hash)
{
}
};
using UCharBuffer = HashTranslatorCharBuffer<UChar>;
struct UCharBufferTranslator {
static unsigned hash(const UCharBuffer& buf)
{
return buf.hash;
}
static bool equal(StringImpl* const& str, const UCharBuffer& buf)
{
return WTF::equal(str, buf.characters, buf.length);
}
static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
{
location = &StringImpl::create8BitIfPossible(buf.characters, buf.length).leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
struct HashAndUTF8Characters {
unsigned hash;
const char* characters;
unsigned length;
unsigned utf16Length;
};
struct HashAndUTF8CharactersTranslator {
static unsigned hash(const HashAndUTF8Characters& buffer)
{
return buffer.hash;
}
static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
{
if (buffer.utf16Length != string->length())
return false;
// If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
if (buffer.utf16Length != buffer.length) {
if (string->is8Bit())
return equalLatin1WithUTF8(string->characters8(), buffer.characters, buffer.characters + buffer.length);
return equalUTF16WithUTF8(string->characters16(), buffer.characters, buffer.characters + buffer.length);
}
if (string->is8Bit()) {
const LChar* stringCharacters = string->characters8();
for (unsigned i = 0; i < buffer.length; ++i) {
ASSERT(isASCII(buffer.characters[i]));
if (stringCharacters[i] != buffer.characters[i])
return false;
}
return true;
}
const UChar* stringCharacters = string->characters16();
for (unsigned i = 0; i < buffer.length; ++i) {
ASSERT(isASCII(buffer.characters[i]));
if (stringCharacters[i] != buffer.characters[i])
return false;
}
return true;
}
static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
{
UChar* target;
auto newString = StringImpl::createUninitialized(buffer.utf16Length, target);
bool isAllASCII;
const char* source = buffer.characters;
if (!convertUTF8ToUTF16(source, source + buffer.length, &target, target + buffer.utf16Length, &isAllASCII))
ASSERT_NOT_REACHED();
if (isAllASCII)
newString = StringImpl::create(buffer.characters, buffer.length);
location = &newString.leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
RefPtr<AtomStringImpl> AtomStringImpl::add(const UChar* characters, unsigned length)
{
if (!characters)
return nullptr;
if (!length)
return static_cast<AtomStringImpl*>(StringImpl::empty());
UCharBuffer buffer { characters, length };
return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
}
RefPtr<AtomStringImpl> AtomStringImpl::add(const UChar* characters)
{
if (!characters)
return nullptr;
unsigned length = 0;
while (characters[length] != UChar(0))
++length;
if (!length)
return static_cast<AtomStringImpl*>(StringImpl::empty());
UCharBuffer buffer { characters, length };
return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
}
struct SubstringLocation {
StringImpl* baseString;
unsigned start;
unsigned length;
};
struct SubstringTranslator {
static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
{
location = &StringImpl::createSubstringSharingImpl(*buffer.baseString, buffer.start, buffer.length).leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
struct SubstringTranslator8 : SubstringTranslator {
static unsigned hash(const SubstringLocation& buffer)
{
return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters8() + buffer.start, buffer.length);
}
static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
{
return WTF::equal(string, buffer.baseString->characters8() + buffer.start, buffer.length);
}
};
struct SubstringTranslator16 : SubstringTranslator {
static unsigned hash(const SubstringLocation& buffer)
{
return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters16() + buffer.start, buffer.length);
}
static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
{
return WTF::equal(string, buffer.baseString->characters16() + buffer.start, buffer.length);
}
};
RefPtr<AtomStringImpl> AtomStringImpl::add(StringImpl* baseString, unsigned start, unsigned length)
{
if (!baseString)
return nullptr;
if (!length || start >= baseString->length())
return static_cast<AtomStringImpl*>(StringImpl::empty());
unsigned maxLength = baseString->length() - start;
if (length >= maxLength) {
if (!start)
return add(baseString);
length = maxLength;
}
SubstringLocation buffer = { baseString, start, length };
if (baseString->is8Bit())
return addToStringTable<SubstringLocation, SubstringTranslator8>(buffer);
return addToStringTable<SubstringLocation, SubstringTranslator16>(buffer);
}
using LCharBuffer = HashTranslatorCharBuffer<LChar>;
struct LCharBufferTranslator {
static unsigned hash(const LCharBuffer& buf)
{
return buf.hash;
}
static bool equal(StringImpl* const& str, const LCharBuffer& buf)
{
return WTF::equal(str, buf.characters, buf.length);
}
static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
{
location = &StringImpl::create(buf.characters, buf.length).leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
template<typename CharType>
struct BufferFromStaticDataTranslator {
using Buffer = HashTranslatorCharBuffer<CharType>;
static unsigned hash(const Buffer& buf)
{
return buf.hash;
}
static bool equal(StringImpl* const& str, const Buffer& buf)
{
return WTF::equal(str, buf.characters, buf.length);
}
static void translate(StringImpl*& location, const Buffer& buf, unsigned hash)
{
location = &StringImpl::createWithoutCopying(buf.characters, buf.length).leakRef();
location->setHash(hash);
location->setIsAtomic(true);
}
};
RefPtr<AtomStringImpl> AtomStringImpl::add(const LChar* characters, unsigned length)
{
if (!characters)
return nullptr;
if (!length)
return static_cast<AtomStringImpl*>(StringImpl::empty());
LCharBuffer buffer { characters, length };
return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
}
Ref<AtomStringImpl> AtomStringImpl::addLiteral(const char* characters, unsigned length)
{
ASSERT(characters);
ASSERT(length);
LCharBuffer buffer { reinterpret_cast<const LChar*>(characters), length };
return addToStringTable<LCharBuffer, BufferFromStaticDataTranslator<LChar>>(buffer);
}
static Ref<AtomStringImpl> addSymbol(AtomStringTableLocker& locker, StringTableImpl& atomStringTable, StringImpl& base)
{
ASSERT(base.length());
ASSERT(base.isSymbol());
SubstringLocation buffer = { &base, 0, base.length() };
if (base.is8Bit())
return addToStringTable<SubstringLocation, SubstringTranslator8>(locker, atomStringTable, buffer);
return addToStringTable<SubstringLocation, SubstringTranslator16>(locker, atomStringTable, buffer);
}
static inline Ref<AtomStringImpl> addSymbol(StringImpl& base)
{
AtomStringTableLocker locker;
return addSymbol(locker, stringTable(), base);
}
static Ref<AtomStringImpl> addStatic(AtomStringTableLocker& locker, StringTableImpl& atomStringTable, const StringImpl& base)
{
ASSERT(base.length());
ASSERT(base.isStatic());
if (base.is8Bit()) {
LCharBuffer buffer { base.characters8(), base.length(), base.hash() };
return addToStringTable<LCharBuffer, BufferFromStaticDataTranslator<LChar>>(locker, atomStringTable, buffer);
}
UCharBuffer buffer { base.characters16(), base.length(), base.hash() };
return addToStringTable<UCharBuffer, BufferFromStaticDataTranslator<UChar>>(locker, atomStringTable, buffer);
}
static inline Ref<AtomStringImpl> addStatic(const StringImpl& base)
{
AtomStringTableLocker locker;
return addStatic(locker, stringTable(), base);
}
RefPtr<AtomStringImpl> AtomStringImpl::add(const StaticStringImpl* string)
{
auto s = reinterpret_cast<const StringImpl*>(string);
ASSERT(s->isStatic());
return addStatic(*s);
}
Ref<AtomStringImpl> AtomStringImpl::addSlowCase(StringImpl& string)
{
// This check is necessary for null symbols.
// Their length is zero, but they are not AtomStringImpl.
if (!string.length())
return *static_cast<AtomStringImpl*>(StringImpl::empty());
if (string.isStatic())
return addStatic(string);
if (string.isSymbol())
return addSymbol(string);
ASSERT_WITH_MESSAGE(!string.isAtom(), "AtomStringImpl should not hit the slow case if the string is already atomic.");
AtomStringTableLocker locker;
auto addResult = stringTable().add(&string);
if (addResult.isNewEntry) {
ASSERT(*addResult.iterator == &string);
string.setIsAtomic(true);
}
return *static_cast<AtomStringImpl*>(*addResult.iterator);
}
Ref<AtomStringImpl> AtomStringImpl::addSlowCase(AtomStringTable& stringTable, StringImpl& string)
{
// This check is necessary for null symbols.
// Their length is zero, but they are not AtomStringImpl.
if (!string.length())
return *static_cast<AtomStringImpl*>(StringImpl::empty());
if (string.isStatic()) {
AtomStringTableLocker locker;
return addStatic(locker, stringTable.table(), string);
}
if (string.isSymbol()) {
AtomStringTableLocker locker;
return addSymbol(locker, stringTable.table(), string);
}
ASSERT_WITH_MESSAGE(!string.isAtom(), "AtomStringImpl should not hit the slow case if the string is already atomic.");
AtomStringTableLocker locker;
auto addResult = stringTable.table().add(&string);
if (addResult.isNewEntry) {
ASSERT(*addResult.iterator == &string);
string.setIsAtomic(true);
}
return *static_cast<AtomStringImpl*>(*addResult.iterator);
}
void AtomStringImpl::remove(AtomStringImpl* string)
{
ASSERT(string->isAtom());
AtomStringTableLocker locker;
auto& atomStringTable = stringTable();
auto iterator = atomStringTable.find(string);
ASSERT_WITH_MESSAGE(iterator != atomStringTable.end(), "The string being removed is atomic in the string table of an other thread!");
ASSERT(string == *iterator);
atomStringTable.remove(iterator);
}
RefPtr<AtomStringImpl> AtomStringImpl::lookUpSlowCase(StringImpl& string)
{
ASSERT_WITH_MESSAGE(!string.isAtom(), "AtomicStringImpls should return from the fast case.");
if (!string.length())
return static_cast<AtomStringImpl*>(StringImpl::empty());
AtomStringTableLocker locker;
auto& atomStringTable = stringTable();
auto iterator = atomStringTable.find(&string);
if (iterator != atomStringTable.end())
return static_cast<AtomStringImpl*>(*iterator);
return nullptr;
}
RefPtr<AtomStringImpl> AtomStringImpl::addUTF8(const char* charactersStart, const char* charactersEnd)
{
HashAndUTF8Characters buffer;
buffer.characters = charactersStart;
buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
if (!buffer.hash)
return nullptr;
return addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
}
RefPtr<AtomStringImpl> AtomStringImpl::lookUp(const LChar* characters, unsigned length)
{
AtomStringTableLocker locker;
auto& table = stringTable();
LCharBuffer buffer = { characters, length };
auto iterator = table.find<LCharBufferTranslator>(buffer);
if (iterator != table.end())
return static_cast<AtomStringImpl*>(*iterator);
return nullptr;
}
RefPtr<AtomStringImpl> AtomStringImpl::lookUp(const UChar* characters, unsigned length)
{
AtomStringTableLocker locker;
auto& table = stringTable();
UCharBuffer buffer { characters, length };
auto iterator = table.find<UCharBufferTranslator>(buffer);
if (iterator != table.end())
return static_cast<AtomStringImpl*>(*iterator);
return nullptr;
}
#if !ASSERT_DISABLED
bool AtomStringImpl::isInAtomStringTable(StringImpl* string)
{
AtomStringTableLocker locker;
return stringTable().contains(string);
}
#endif
} // namespace WTF