runtime/UStringImpl.h

   1 /*
   2  * Copyright (C) 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef UStringImpl_h
  27 #define UStringImpl_h
  28
  29 #include <limits>
  30 #include <wtf/CrossThreadRefCounted.h>
  31 #include <wtf/OwnFastMallocPtr.h>
  32 #include <wtf/PossiblyNull.h>
  33 #include <wtf/StringHashFunctions.h>
  34 #include <wtf/Vector.h>
  35 #include <wtf/unicode/Unicode.h>
  36
  37 namespace JSC {
  38
  39 class IdentifierTable;
  40
  41 typedef CrossThreadRefCounted<OwnFastMallocPtr<UChar> > SharedUChar;
  42
  43 class UntypedPtrAndBitfield {
  44 public:
  45     UntypedPtrAndBitfield() {}
  46
  47     UntypedPtrAndBitfield(void* ptrValue, uintptr_t bitValue)
  48         : m_value(reinterpret_cast<uintptr_t>(ptrValue) | bitValue)
  49 #ifndef NDEBUG
  50         , m_leaksPtr(ptrValue)
  51 #endif
  52     {
  53         ASSERT(ptrValue == asPtr<void*>());
  54         ASSERT((*this & ~s_alignmentMask) == bitValue);
  55     }
  56
  57     template<typename T>
  58     T asPtr() const { return reinterpret_cast<T>(m_value & s_alignmentMask); }
  59
  60     UntypedPtrAndBitfield& operator&=(uintptr_t bits)
  61     {
  62         m_value &= bits | s_alignmentMask;
  63         return *this;
  64     }
  65
  66     UntypedPtrAndBitfield& operator|=(uintptr_t bits)
  67     {
  68         m_value |= bits & ~s_alignmentMask;
  69         return *this;
  70     }
  71
  72     uintptr_t operator&(uintptr_t mask) const
  73     {
  74         return m_value & mask & ~s_alignmentMask;
  75     }
  76
  77 private:
  78     static const uintptr_t s_alignmentMask = ~static_cast<uintptr_t>(0x7);
  79     uintptr_t m_value;
  80 #ifndef NDEBUG
  81         void* m_leaksPtr; // Only used to allow tools like leaks on OSX to detect that the memory is referenced.
  82 #endif
  83 };
  84
  85 class UStringImpl : Noncopyable {
  86 public:
  87     template<size_t inlineCapacity>
  88     static PassRefPtr<UStringImpl> adopt(Vector<UChar, inlineCapacity>& vector)
  89     {
  90         if (unsigned length = vector.size())
  91             return adoptRef(new UStringImpl(vector.releaseBuffer(), length, BufferOwned));
  92         return &empty();
  93     }
  94
  95     static PassRefPtr<UStringImpl> create(const UChar* buffer, int length)
  96     {
  97         UChar* newBuffer;
  98         if (PassRefPtr<UStringImpl> impl = tryCreateUninitialized(length, newBuffer)) {
  99             copyChars(newBuffer, buffer, length);
 100             return impl;
 101         }
 102         return &null();
 103     }
 104
 105     static PassRefPtr<UStringImpl> create(PassRefPtr<UStringImpl> rep, int offset, int length)
 106     {
 107         ASSERT(rep);
 108         rep->checkConsistency();
 109         return adoptRef(new UStringImpl(rep->m_data + offset, length, rep->bufferOwnerString()));
 110     }
 111
 112     static PassRefPtr<UStringImpl> create(PassRefPtr<SharedUChar> sharedBuffer, UChar* buffer, int length)
 113     {
 114         return adoptRef(new UStringImpl(buffer, length, sharedBuffer));
 115     }
 116
 117     static PassRefPtr<UStringImpl> createUninitialized(unsigned length, UChar*& output)
 118     {
 119         if (!length) {
 120             output = 0;
 121             return &empty();
 122         }
 123
 124         if (length > ((std::numeric_limits<size_t>::max() - sizeof(UStringImpl)) / sizeof(UChar)))
 125             CRASH();
 126         UStringImpl* resultImpl = static_cast<UStringImpl*>(fastMalloc(sizeof(UChar) * length + sizeof(UStringImpl)));
 127         output = reinterpret_cast<UChar*>(resultImpl + 1);
 128         return adoptRef(new(resultImpl) UStringImpl(output, length, BufferInternal));
 129     }
 130
 131     static PassRefPtr<UStringImpl> tryCreateUninitialized(unsigned length, UChar*& output)
 132     {
 133         if (!length) {
 134             output = 0;
 135             return &empty();
 136         }
 137
 138         if (length > ((std::numeric_limits<size_t>::max() - sizeof(UStringImpl)) / sizeof(UChar)))
 139             return 0;
 140         UStringImpl* resultImpl;
 141         if (!tryFastMalloc(sizeof(UChar) * length + sizeof(UStringImpl)).getValue(resultImpl))
 142             return 0;
 143         output = reinterpret_cast<UChar*>(resultImpl + 1);
 144         return adoptRef(new(resultImpl) UStringImpl(output, length, BufferInternal));
 145     }
 146
 147     SharedUChar* sharedBuffer();
 148     UChar* data() const { return m_data; }
 149     int size() const { return m_length; }
 150     size_t cost()
 151     {
 152         // For substrings, return the cost of the base string.
 153         if (bufferOwnership() == BufferSubstring)
 154             return m_dataBuffer.asPtr<UStringImpl*>()->cost();
 155
 156         if (m_dataBuffer & s_reportedCostBit)
 157             return 0;
 158         m_dataBuffer |= s_reportedCostBit;
 159         return m_length;
 160     }
 161     unsigned hash() const { if (!m_hash) m_hash = computeHash(data(), m_length); return m_hash; }
 162     unsigned existingHash() const { ASSERT(m_hash); return m_hash; } // fast path for Identifiers
 163     void setHash(unsigned hash) { ASSERT(hash == computeHash(data(), m_length)); m_hash = hash; } // fast path for Identifiers
 164     bool isIdentifier() const { return m_isIdentifier; }
 165     void setIsIdentifier(bool isIdentifier) { m_isIdentifier = isIdentifier; }
 166
 167     UStringImpl* ref() { m_refCount += s_refCountIncrement; return this; }
 168     ALWAYS_INLINE void deref() { if (!(m_refCount -= s_refCountIncrement)) delete this; }
 169
 170     static void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
 171     {
 172         if (numCharacters <= s_copyCharsInlineCutOff) {
 173             for (unsigned i = 0; i < numCharacters; ++i)
 174                 destination[i] = source[i];
 175         } else
 176             memcpy(destination, source, numCharacters * sizeof(UChar));
 177     }
 178
 179     static unsigned computeHash(const UChar* s, int length) { ASSERT(length >= 0); return WTF::stringHash(s, length); }
 180     static unsigned computeHash(const char* s, int length) { ASSERT(length >= 0); return WTF::stringHash(s, length); }
 181     static unsigned computeHash(const char* s) { return WTF::stringHash(s); }
 182
 183     static UStringImpl& null() { return *s_null; }
 184     static UStringImpl& empty() { return *s_empty; }
 185
 186     ALWAYS_INLINE void checkConsistency() const
 187     {
 188         // There is no recursion of substrings.
 189         ASSERT(bufferOwnerString()->bufferOwnership() != BufferSubstring);
 190         // Static strings cannot be put in identifier tables, because they are globally shared.
 191         ASSERT(!isStatic() || !isIdentifier());
 192     }
 193
 194 private:
 195     enum BufferOwnership {
 196         BufferInternal,
 197         BufferOwned,
 198         BufferSubstring,
 199         BufferShared,
 200     };
 201
 202     // For SmallStringStorage, which allocates an array and uses an in-place new.
 203     UStringImpl() { }
 204
 205     // Used to construct normal strings with an internal or external buffer.
 206     UStringImpl(UChar* data, int length, BufferOwnership ownership)
 207         : m_data(data)
 208         , m_length(length)
 209         , m_refCount(s_refCountIncrement)
 210         , m_hash(0)
 211         , m_isIdentifier(false)
 212         , m_dataBuffer(0, ownership)
 213     {
 214         ASSERT((ownership == BufferInternal) || (ownership == BufferOwned));
 215         checkConsistency();
 216     }
 217
 218     // Used to construct static strings, which have an special refCount that can never hit zero.
 219     // This means that the static string will never be destroyed, which is important because
 220     // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
 221     enum StaticStringConstructType { ConstructStaticString };
 222     UStringImpl(UChar* data, int length, StaticStringConstructType)
 223         : m_data(data)
 224         , m_length(length)
 225         , m_refCount(s_staticRefCountInitialValue)
 226         , m_hash(0)
 227         , m_isIdentifier(false)
 228         , m_dataBuffer(0, BufferOwned)
 229     {
 230         checkConsistency();
 231     }
 232
 233     // Used to create new strings that are a substring of an existing string.
 234     UStringImpl(UChar* data, int length, PassRefPtr<UStringImpl> base)
 235         : m_data(data)
 236         , m_length(length)
 237         , m_refCount(s_refCountIncrement)
 238         , m_hash(0)
 239         , m_isIdentifier(false)
 240         , m_dataBuffer(base.releaseRef(), BufferSubstring)
 241     {
 242         // Do use static strings as a base for substrings; UntypedPtrAndBitfield assumes
 243         // that all pointers will be at least 8-byte aligned, we cannot guarantee that of
 244         // UStringImpls that are not heap allocated.
 245         ASSERT(m_dataBuffer.asPtr<UStringImpl*>()->size());
 246         ASSERT(!m_dataBuffer.asPtr<UStringImpl*>()->isStatic());
 247         checkConsistency();
 248     }
 249
 250     // Used to construct new strings sharing an existing shared buffer.
 251     UStringImpl(UChar* data, int length, PassRefPtr<SharedUChar> sharedBuffer)
 252         : m_data(data)
 253         , m_length(length)
 254         , m_refCount(s_refCountIncrement)
 255         , m_hash(0)
 256         , m_isIdentifier(false)
 257         , m_dataBuffer(sharedBuffer.releaseRef(), BufferShared)
 258     {
 259         checkConsistency();
 260     }
 261
 262     using Noncopyable::operator new;
 263     void* operator new(size_t, void* inPlace) { return inPlace; }
 264
 265     ~UStringImpl();
 266
 267     // This number must be at least 2 to avoid sharing empty, null as well as 1 character strings from SmallStrings.
 268     static const int s_minLengthToShare = 10;
 269     static const unsigned s_copyCharsInlineCutOff = 20;
 270     static const uintptr_t s_bufferOwnershipMask = 3;
 271     static const uintptr_t s_reportedCostBit = 4;
 272     // We initialize and increment/decrement the refCount for all normal (non-static) strings by the value 2.
 273     // We initialize static strings with an odd number (specifically, 1), such that the refCount cannot reach zero.
 274     static const int s_refCountIncrement = 2;
 275     static const int s_staticRefCountInitialValue = 1;
 276
 277     UStringImpl* bufferOwnerString() { return (bufferOwnership() == BufferSubstring) ? m_dataBuffer.asPtr<UStringImpl*>() :  this; }
 278     const UStringImpl* bufferOwnerString() const { return (bufferOwnership() == BufferSubstring) ? m_dataBuffer.asPtr<UStringImpl*>() :  this; }
 279     SharedUChar* baseSharedBuffer();
 280     unsigned bufferOwnership() const { return m_dataBuffer & s_bufferOwnershipMask; }
 281     bool isStatic() const { return m_refCount & 1; }
 282
 283     // unshared data
 284     UChar* m_data;
 285     int m_length;
 286     unsigned m_refCount;
 287     mutable unsigned m_hash : 31;
 288     mutable unsigned m_isIdentifier : 1;
 289     UntypedPtrAndBitfield m_dataBuffer;
 290
 291     JS_EXPORTDATA static UStringImpl* s_null;
 292     JS_EXPORTDATA static UStringImpl* s_empty;
 293
 294     friend class JIT;
 295     friend class SmallStringsStorage;
 296     friend void initializeUString();
 297 };
 298
 299 bool equal(const UStringImpl*, const UStringImpl*);
 300
 301 }
 302
 303 #endif