6de87c847d00d8ba7ab302f414ea6b248885321d
[WebKit-https.git] / Source / JavaScriptCore / wtf / text / StringImpl.h
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
4  * Copyright (C) 2009 Google Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #ifndef StringImpl_h
24 #define StringImpl_h
25
26 #include <limits.h>
27 #include <wtf/ASCIICType.h>
28 #include <wtf/CrossThreadRefCounted.h>
29 #include <wtf/Forward.h>
30 #include <wtf/OwnFastMallocPtr.h>
31 #include <wtf/StdLibExtras.h>
32 #include <wtf/StringHasher.h>
33 #include <wtf/Vector.h>
34 #include <wtf/text/StringImplBase.h>
35 #include <wtf/unicode/Unicode.h>
36
37 #if PLATFORM(CF)
38 typedef const struct __CFString * CFStringRef;
39 #endif
40
41 #ifdef __OBJC__
42 @class NSString;
43 #endif
44
45 // FIXME: This is a temporary layering violation while we move string code to WTF.
46 // Landing the file moves in one patch, will follow on with patches to change the namespaces.
47 namespace JSC {
48 struct IdentifierCStringTranslator;
49 struct IdentifierUCharBufferTranslator;
50 }
51
52 namespace WTF {
53
54 struct CStringTranslator;
55 struct HashAndCharactersTranslator;
56 struct HashAndUTF8CharactersTranslator;
57 struct UCharBufferTranslator;
58
59 enum TextCaseSensitivity { TextCaseSensitive, TextCaseInsensitive };
60
61 typedef OwnFastMallocPtr<const UChar> SharableUChar;
62 typedef CrossThreadRefCounted<SharableUChar> SharedUChar;
63 typedef bool (*CharacterMatchFunctionPtr)(UChar);
64
65 class StringImpl : public StringImplBase {
66     friend struct JSC::IdentifierCStringTranslator;
67     friend struct JSC::IdentifierUCharBufferTranslator;
68     friend struct WTF::CStringTranslator;
69     friend struct WTF::HashAndCharactersTranslator;
70     friend struct WTF::HashAndUTF8CharactersTranslator;
71     friend struct WTF::UCharBufferTranslator;
72     friend class AtomicStringImpl;
73 private:
74     // Used to construct static strings, which have an special refCount that can never hit zero.
75     // This means that the static string will never be destroyed, which is important because
76     // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
77     StringImpl(const UChar* characters, unsigned length, StaticStringConstructType)
78         : StringImplBase(length, ConstructStaticString)
79         , m_data(characters)
80         , m_buffer(0)
81         , m_hash(0)
82     {
83         // Ensure that the hash is computed so that AtomicStringHash can call existingHash()
84         // with impunity. The empty string is special because it is never entered into
85         // AtomicString's HashKey, but still needs to compare correctly.
86         hash();
87     }
88
89     // Create a normal string with internal storage (BufferInternal)
90     StringImpl(unsigned length)
91         : StringImplBase(length, BufferInternal)
92         , m_data(reinterpret_cast<const UChar*>(this + 1))
93         , m_buffer(0)
94         , m_hash(0)
95     {
96         ASSERT(m_data);
97         ASSERT(m_length);
98     }
99
100     // Create a StringImpl adopting ownership of the provided buffer (BufferOwned)
101     StringImpl(const UChar* characters, unsigned length)
102         : StringImplBase(length, BufferOwned)
103         , m_data(characters)
104         , m_buffer(0)
105         , m_hash(0)
106     {
107         ASSERT(m_data);
108         ASSERT(m_length);
109     }
110
111     // Used to create new strings that are a substring of an existing StringImpl (BufferSubstring)
112     StringImpl(const UChar* characters, unsigned length, PassRefPtr<StringImpl> base)
113         : StringImplBase(length, BufferSubstring)
114         , m_data(characters)
115         , m_substringBuffer(base.leakRef())
116         , m_hash(0)
117     {
118         ASSERT(m_data);
119         ASSERT(m_length);
120         ASSERT(m_substringBuffer->bufferOwnership() != BufferSubstring);
121     }
122
123     // Used to construct new strings sharing an existing SharedUChar (BufferShared)
124     StringImpl(const UChar* characters, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)
125         : StringImplBase(length, BufferShared)
126         , m_data(characters)
127         , m_sharedBuffer(sharedBuffer.leakRef())
128         , m_hash(0)
129     {
130         ASSERT(m_data);
131         ASSERT(m_length);
132     }
133
134     // For use only by AtomicString's XXXTranslator helpers.
135     void setHash(unsigned hash)
136     {
137         ASSERT(!isStatic());
138         ASSERT(!m_hash);
139         ASSERT(hash == computeHash(m_data, m_length));
140         m_hash = hash;
141     }
142
143 public:
144     ~StringImpl();
145
146     static PassRefPtr<StringImpl> create(const UChar*, unsigned length);
147     static PassRefPtr<StringImpl> create(const char*, unsigned length);
148     static PassRefPtr<StringImpl> create(const char*);
149     static PassRefPtr<StringImpl> create(const UChar*, unsigned length, PassRefPtr<SharedUChar> sharedBuffer);
150     static ALWAYS_INLINE PassRefPtr<StringImpl> create(PassRefPtr<StringImpl> rep, unsigned offset, unsigned length)
151     {
152         ASSERT(rep);
153         ASSERT(length <= rep->length());
154
155         if (!length)
156             return empty();
157
158         StringImpl* ownerRep = (rep->bufferOwnership() == BufferSubstring) ? rep->m_substringBuffer : rep.get();
159         return adoptRef(new StringImpl(rep->m_data + offset, length, ownerRep));
160     }
161
162     static PassRefPtr<StringImpl> createUninitialized(unsigned length, UChar*& data);
163     static ALWAYS_INLINE PassRefPtr<StringImpl> tryCreateUninitialized(unsigned length, UChar*& output)
164     {
165         if (!length) {
166             output = 0;
167             return empty();
168         }
169
170         if (length > ((std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(UChar))) {
171             output = 0;
172             return 0;
173         }
174         StringImpl* resultImpl;
175         if (!tryFastMalloc(sizeof(UChar) * length + sizeof(StringImpl)).getValue(resultImpl)) {
176             output = 0;
177             return 0;
178         }
179         output = reinterpret_cast<UChar*>(resultImpl + 1);
180         return adoptRef(new(resultImpl) StringImpl(length));
181     }
182
183     static unsigned dataOffset() { return OBJECT_OFFSETOF(StringImpl, m_data); }
184     static PassRefPtr<StringImpl> createWithTerminatingNullCharacter(const StringImpl&);
185     static PassRefPtr<StringImpl> createStrippingNullCharacters(const UChar*, unsigned length);
186
187     template<size_t inlineCapacity>
188     static PassRefPtr<StringImpl> adopt(Vector<UChar, inlineCapacity>& vector)
189     {
190         if (size_t size = vector.size()) {
191             ASSERT(vector.data());
192             if (size > std::numeric_limits<unsigned>::max())
193                 CRASH();
194             return adoptRef(new StringImpl(vector.releaseBuffer(), size));
195         }
196         return empty();
197     }
198     static PassRefPtr<StringImpl> adopt(StringBuffer&);
199
200     SharedUChar* sharedBuffer();
201     const UChar* characters() const { return m_data; }
202
203     size_t cost()
204     {
205         // For substrings, return the cost of the base string.
206         if (bufferOwnership() == BufferSubstring)
207             return m_substringBuffer->cost();
208
209         if (m_refCountAndFlags & s_refCountFlagShouldReportedCost) {
210             m_refCountAndFlags &= ~s_refCountFlagShouldReportedCost;
211             return m_length;
212         }
213         return 0;
214     }
215
216     bool isIdentifier() const { return m_refCountAndFlags & s_refCountFlagIsIdentifier; }
217     void setIsIdentifier(bool isIdentifier)
218     {
219         ASSERT(!isStatic());
220         if (isIdentifier)
221             m_refCountAndFlags |= s_refCountFlagIsIdentifier;
222         else
223             m_refCountAndFlags &= ~s_refCountFlagIsIdentifier;
224     }
225
226     bool hasTerminatingNullCharacter() const { return m_refCountAndFlags & s_refCountFlagHasTerminatingNullCharacter; }
227
228     bool isAtomic() const { return m_refCountAndFlags & s_refCountFlagIsAtomic; }
229     void setIsAtomic(bool isIdentifier)
230     {
231         ASSERT(!isStatic());
232         if (isIdentifier)
233             m_refCountAndFlags |= s_refCountFlagIsAtomic;
234         else
235             m_refCountAndFlags &= ~s_refCountFlagIsAtomic;
236     }
237
238     unsigned hash() const { if (!m_hash) m_hash = computeHash(m_data, m_length); return m_hash; }
239     unsigned existingHash() const { ASSERT(m_hash); return m_hash; }
240     static unsigned computeHash(const UChar* data, unsigned length) { return WTF::StringHasher::createHash<UChar>(data, length); }
241     static unsigned computeHash(const char* data, unsigned length) { return WTF::StringHasher::createHash<char>(data, length); }
242     static unsigned computeHash(const char* data) { return WTF::StringHasher::createHash<char>(data); }
243
244     ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic))) delete this; }
245     ALWAYS_INLINE bool hasOneRef() const { return (m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic)) == s_refCountIncrement; }
246
247     static StringImpl* empty();
248
249     static void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
250     {
251         if (numCharacters <= s_copyCharsInlineCutOff) {
252             for (unsigned i = 0; i < numCharacters; ++i)
253                 destination[i] = source[i];
254         } else
255             memcpy(destination, source, numCharacters * sizeof(UChar));
256     }
257
258     // Returns a StringImpl suitable for use on another thread.
259     PassRefPtr<StringImpl> crossThreadString();
260     // Makes a deep copy. Helpful only if you need to use a String on another thread
261     // (use crossThreadString if the method call doesn't need to be threadsafe).
262     // Since StringImpl objects are immutable, there's no other reason to make a copy.
263     PassRefPtr<StringImpl> threadsafeCopy() const;
264
265     PassRefPtr<StringImpl> substring(unsigned pos, unsigned len = UINT_MAX);
266
267     UChar operator[](unsigned i) { ASSERT(i < m_length); return m_data[i]; }
268     UChar32 characterStartingAt(unsigned);
269
270     bool containsOnlyWhitespace();
271
272     int toIntStrict(bool* ok = 0, int base = 10);
273     unsigned toUIntStrict(bool* ok = 0, int base = 10);
274     int64_t toInt64Strict(bool* ok = 0, int base = 10);
275     uint64_t toUInt64Strict(bool* ok = 0, int base = 10);
276     intptr_t toIntPtrStrict(bool* ok = 0, int base = 10);
277
278     int toInt(bool* ok = 0); // ignores trailing garbage
279     unsigned toUInt(bool* ok = 0); // ignores trailing garbage
280     int64_t toInt64(bool* ok = 0); // ignores trailing garbage
281     uint64_t toUInt64(bool* ok = 0); // ignores trailing garbage
282     intptr_t toIntPtr(bool* ok = 0); // ignores trailing garbage
283
284     double toDouble(bool* ok = 0);
285     float toFloat(bool* ok = 0);
286
287     PassRefPtr<StringImpl> lower();
288     PassRefPtr<StringImpl> upper();
289
290     enum LastCharacterBehavior { ObscureLastCharacter, DisplayLastCharacter };
291
292     PassRefPtr<StringImpl> secure(UChar, LastCharacterBehavior = ObscureLastCharacter);
293     PassRefPtr<StringImpl> foldCase();
294
295     PassRefPtr<StringImpl> stripWhiteSpace();
296     PassRefPtr<StringImpl> simplifyWhiteSpace();
297
298     PassRefPtr<StringImpl> removeCharacters(CharacterMatchFunctionPtr);
299
300     size_t find(UChar, unsigned index = 0);
301     size_t find(CharacterMatchFunctionPtr, unsigned index = 0);
302     size_t find(const char*, unsigned index = 0);
303     size_t find(StringImpl*, unsigned index = 0);
304     size_t findIgnoringCase(const char*, unsigned index = 0);
305     size_t findIgnoringCase(StringImpl*, unsigned index = 0);
306
307     size_t reverseFind(UChar, unsigned index = UINT_MAX);
308     size_t reverseFind(StringImpl*, unsigned index = UINT_MAX);
309     size_t reverseFindIgnoringCase(StringImpl*, unsigned index = UINT_MAX);
310
311     bool startsWith(StringImpl* str, bool caseSensitive = true) { return (caseSensitive ? reverseFind(str, 0) : reverseFindIgnoringCase(str, 0)) == 0; }
312     bool endsWith(StringImpl*, bool caseSensitive = true);
313
314     PassRefPtr<StringImpl> replace(UChar, UChar);
315     PassRefPtr<StringImpl> replace(UChar, StringImpl*);
316     PassRefPtr<StringImpl> replace(StringImpl*, StringImpl*);
317     PassRefPtr<StringImpl> replace(unsigned index, unsigned len, StringImpl*);
318
319     WTF::Unicode::Direction defaultWritingDirection(bool* hasStrongDirectionality = 0);
320
321 #if PLATFORM(CF)
322     CFStringRef createCFString();
323 #endif
324 #ifdef __OBJC__
325     operator NSString*();
326 #endif
327
328 private:
329     // This number must be at least 2 to avoid sharing empty, null as well as 1 character strings from SmallStrings.
330     static const unsigned s_copyCharsInlineCutOff = 20;
331
332     static PassRefPtr<StringImpl> createStrippingNullCharactersSlowCase(const UChar*, unsigned length);
333     
334     BufferOwnership bufferOwnership() const { return static_cast<BufferOwnership>(m_refCountAndFlags & s_refCountMaskBufferOwnership); }
335     bool isStatic() const { return m_refCountAndFlags & s_refCountFlagStatic; }
336     const UChar* m_data;
337     union {
338         void* m_buffer;
339         StringImpl* m_substringBuffer;
340         SharedUChar* m_sharedBuffer;
341     };
342     mutable unsigned m_hash;
343 };
344
345 bool equal(const StringImpl*, const StringImpl*);
346 bool equal(const StringImpl*, const char*);
347 inline bool equal(const char* a, StringImpl* b) { return equal(b, a); }
348
349 bool equalIgnoringCase(StringImpl*, StringImpl*);
350 bool equalIgnoringCase(StringImpl*, const char*);
351 inline bool equalIgnoringCase(const char* a, StringImpl* b) { return equalIgnoringCase(b, a); }
352 bool equalIgnoringCase(const UChar* a, const char* b, unsigned length);
353 inline bool equalIgnoringCase(const char* a, const UChar* b, unsigned length) { return equalIgnoringCase(b, a, length); }
354
355 bool equalIgnoringNullity(StringImpl*, StringImpl*);
356
357 template<size_t inlineCapacity>
358 bool equalIgnoringNullity(const Vector<UChar, inlineCapacity>& a, StringImpl* b)
359 {
360     if (!b)
361         return !a.size();
362     if (a.size() != b->length())
363         return false;
364     return !memcmp(a.data(), b->characters(), b->length());
365 }
366
367 int codePointCompare(const StringImpl*, const StringImpl*);
368
369 static inline bool isSpaceOrNewline(UChar c)
370 {
371     // Use isASCIISpace() for basic Latin-1.
372     // This will include newlines, which aren't included in Unicode DirWS.
373     return c <= 0x7F ? WTF::isASCIISpace(c) : WTF::Unicode::direction(c) == WTF::Unicode::WhiteSpaceNeutral;
374 }
375
376 // This is a hot function because it's used when parsing HTML.
377 inline PassRefPtr<StringImpl> StringImpl::createStrippingNullCharacters(const UChar* characters, unsigned length)
378 {
379     ASSERT(characters);
380     ASSERT(length);
381
382     // Optimize for the case where there are no Null characters by quickly
383     // searching for nulls, and then using StringImpl::create, which will
384     // memcpy the whole buffer.  This is faster than assigning character by
385     // character during the loop. 
386
387     // Fast case.
388     int foundNull = 0;
389     for (unsigned i = 0; !foundNull && i < length; i++) {
390         int c = characters[i]; // more efficient than using UChar here (at least on Intel Mac OS)
391         foundNull |= !c;
392     }
393     if (!foundNull)
394         return StringImpl::create(characters, length);
395
396     return StringImpl::createStrippingNullCharactersSlowCase(characters, length);
397 }
398
399 struct StringHash;
400
401 // StringHash is the default hash for StringImpl* and RefPtr<StringImpl>
402 template<typename T> struct DefaultHash;
403 template<> struct DefaultHash<StringImpl*> {
404     typedef StringHash Hash;
405 };
406 template<> struct DefaultHash<RefPtr<StringImpl> > {
407     typedef StringHash Hash;
408 };
409
410 }
411
412 using WTF::StringImpl;
413 using WTF::equal;
414 using WTF::TextCaseSensitivity;
415 using WTF::TextCaseSensitive;
416 using WTF::TextCaseInsensitive;
417
418 #endif