Unreviewed, rolling out r220060.
[WebKit.git] / Source / WTF / wtf / text / AtomicStringImpl.cpp
1 /*
2  * Copyright (C) 2004-2008, 2013-2014 Apple Inc. All rights reserved.
3  * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
4  * Copyright (C) 2012 Google Inc. All rights reserved.
5  * Copyright (C) 2015 Yusuke Suzuki<utatane.tea@gmail.com>. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "AtomicStringImpl.h"
26
27 #include "AtomicStringTable.h"
28 #include "CommaPrinter.h"
29 #include "DataLog.h"
30 #include "HashSet.h"
31 #include "IntegerToStringConversion.h"
32 #include "StringHash.h"
33 #include "StringPrintStream.h"
34 #include "Threading.h"
35 #include "WTFThreadData.h"
36 #include <wtf/unicode/UTF8.h>
37
38 #if USE(WEB_THREAD)
39 #include "Lock.h"
40 #endif
41
42 namespace WTF {
43
44 using namespace Unicode;
45
46 #if USE(WEB_THREAD)
47
48 class AtomicStringTableLocker : public LockHolder {
49     WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
50
51     static StaticLock s_stringTableLock;
52 public:
53     AtomicStringTableLocker()
54         : LockHolder(&s_stringTableLock)
55     {
56     }
57 };
58
59 StaticLock AtomicStringTableLocker::s_stringTableLock;
60
61 #else
62
63 class AtomicStringTableLocker {
64     WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
65 public:
66     AtomicStringTableLocker() { }
67 };
68
69 #endif // USE(WEB_THREAD)
70
71 using StringTableImpl = HashSet<StringImpl*>;
72
73 static ALWAYS_INLINE StringTableImpl& stringTable()
74 {
75     return wtfThreadData().atomicStringTable()->table();
76 }
77
78 template<typename T, typename HashTranslator>
79 static inline Ref<AtomicStringImpl> addToStringTable(AtomicStringTableLocker&, StringTableImpl& atomicStringTable, const T& value)
80 {
81     auto addResult = atomicStringTable.add<HashTranslator>(value);
82
83     // If the string is newly-translated, then we need to adopt it.
84     // The boolean in the pair tells us if that is so.
85     if (addResult.isNewEntry)
86         return adoptRef(static_cast<AtomicStringImpl&>(**addResult.iterator));
87     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
88 }
89
90 template<typename T, typename HashTranslator>
91 static inline Ref<AtomicStringImpl> addToStringTable(const T& value)
92 {
93     AtomicStringTableLocker locker;
94     return addToStringTable<T, HashTranslator>(locker, stringTable(), value);
95 }
96
97 struct CStringTranslator {
98     static unsigned hash(const LChar* characters)
99     {
100         return StringHasher::computeHashAndMaskTop8Bits(characters);
101     }
102
103     static inline bool equal(StringImpl* str, const LChar* characters)
104     {
105         return WTF::equal(str, characters);
106     }
107
108     static void translate(StringImpl*& location, const LChar* const& characters, unsigned hash)
109     {
110         location = &StringImpl::create(characters).leakRef();
111         location->setHash(hash);
112         location->setIsAtomic(true);
113     }
114 };
115
116 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* characters)
117 {
118     if (!characters)
119         return nullptr;
120     if (!*characters)
121         return static_cast<AtomicStringImpl*>(StringImpl::empty());
122
123     return addToStringTable<const LChar*, CStringTranslator>(characters);
124 }
125
126 template<typename CharacterType>
127 struct HashTranslatorCharBuffer {
128     const CharacterType* characters;
129     unsigned length;
130     unsigned hash;
131
132     HashTranslatorCharBuffer(const CharacterType* characters, unsigned length)
133         : characters(characters)
134         , length(length)
135         , hash(StringHasher::computeHashAndMaskTop8Bits(characters, length))
136     {
137     }
138
139     HashTranslatorCharBuffer(const CharacterType* characters, unsigned length, unsigned hash)
140         : characters(characters)
141         , length(length)
142         , hash(hash)
143     {
144     }
145 };
146
147 using UCharBuffer = HashTranslatorCharBuffer<UChar>;
148 struct UCharBufferTranslator {
149     static unsigned hash(const UCharBuffer& buf)
150     {
151         return buf.hash;
152     }
153
154     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
155     {
156         return WTF::equal(str, buf.characters, buf.length);
157     }
158
159     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
160     {
161         location = &StringImpl::create8BitIfPossible(buf.characters, buf.length).leakRef();
162         location->setHash(hash);
163         location->setIsAtomic(true);
164     }
165 };
166
167 struct HashAndUTF8Characters {
168     unsigned hash;
169     const char* characters;
170     unsigned length;
171     unsigned utf16Length;
172 };
173
174 struct HashAndUTF8CharactersTranslator {
175     static unsigned hash(const HashAndUTF8Characters& buffer)
176     {
177         return buffer.hash;
178     }
179
180     static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
181     {
182         if (buffer.utf16Length != string->length())
183             return false;
184
185         // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
186         if (buffer.utf16Length != buffer.length) {
187             if (string->is8Bit())
188                 return equalLatin1WithUTF8(string->characters8(), buffer.characters, buffer.characters + buffer.length);
189
190             return equalUTF16WithUTF8(string->characters16(), buffer.characters, buffer.characters + buffer.length);
191         }
192
193         if (string->is8Bit()) {
194             const LChar* stringCharacters = string->characters8();
195
196             for (unsigned i = 0; i < buffer.length; ++i) {
197                 ASSERT(isASCII(buffer.characters[i]));
198                 if (stringCharacters[i] != buffer.characters[i])
199                     return false;
200             }
201
202             return true;
203         }
204
205         const UChar* stringCharacters = string->characters16();
206
207         for (unsigned i = 0; i < buffer.length; ++i) {
208             ASSERT(isASCII(buffer.characters[i]));
209             if (stringCharacters[i] != buffer.characters[i])
210                 return false;
211         }
212
213         return true;
214     }
215
216     static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
217     {
218         UChar* target;
219         auto newString = StringImpl::createUninitialized(buffer.utf16Length, target);
220
221         bool isAllASCII;
222         const char* source = buffer.characters;
223         if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length, &isAllASCII) != conversionOK)
224             ASSERT_NOT_REACHED();
225
226         if (isAllASCII)
227             newString = StringImpl::create(buffer.characters, buffer.length);
228
229         location = &newString.leakRef();
230         location->setHash(hash);
231         location->setIsAtomic(true);
232     }
233 };
234
235 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* characters, unsigned length)
236 {
237     if (!characters)
238         return nullptr;
239
240     if (!length)
241         return static_cast<AtomicStringImpl*>(StringImpl::empty());
242
243     UCharBuffer buffer { characters, length };
244     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
245 }
246
247 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* characters)
248 {
249     if (!characters)
250         return nullptr;
251
252     unsigned length = 0;
253     while (characters[length] != UChar(0))
254         ++length;
255
256     if (!length)
257         return static_cast<AtomicStringImpl*>(StringImpl::empty());
258
259     UCharBuffer buffer { characters, length };
260     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
261 }
262
263 struct SubstringLocation {
264     StringImpl* baseString;
265     unsigned start;
266     unsigned length;
267 };
268
269 struct SubstringTranslator {
270     static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
271     {
272         location = &StringImpl::createSubstringSharingImpl(*buffer.baseString, buffer.start, buffer.length).leakRef();
273         location->setHash(hash);
274         location->setIsAtomic(true);
275     }
276 };
277
278 struct SubstringTranslator8 : SubstringTranslator {
279     static unsigned hash(const SubstringLocation& buffer)
280     {
281         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters8() + buffer.start, buffer.length);
282     }
283
284     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
285     {
286         return WTF::equal(string, buffer.baseString->characters8() + buffer.start, buffer.length);
287     }
288 };
289
290 struct SubstringTranslator16 : SubstringTranslator {
291     static unsigned hash(const SubstringLocation& buffer)
292     {
293         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters16() + buffer.start, buffer.length);
294     }
295
296     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
297     {
298         return WTF::equal(string, buffer.baseString->characters16() + buffer.start, buffer.length);
299     }
300 };
301
302 RefPtr<AtomicStringImpl> AtomicStringImpl::add(StringImpl* baseString, unsigned start, unsigned length)
303 {
304     if (!baseString)
305         return nullptr;
306
307     if (!length || start >= baseString->length())
308         return static_cast<AtomicStringImpl*>(StringImpl::empty());
309
310     unsigned maxLength = baseString->length() - start;
311     if (length >= maxLength) {
312         if (!start)
313             return add(baseString);
314         length = maxLength;
315     }
316
317     SubstringLocation buffer = { baseString, start, length };
318     if (baseString->is8Bit())
319         return addToStringTable<SubstringLocation, SubstringTranslator8>(buffer);
320     return addToStringTable<SubstringLocation, SubstringTranslator16>(buffer);
321 }
322     
323 using LCharBuffer = HashTranslatorCharBuffer<LChar>;
324 struct LCharBufferTranslator {
325     static unsigned hash(const LCharBuffer& buf)
326     {
327         return buf.hash;
328     }
329
330     static bool equal(StringImpl* const& str, const LCharBuffer& buf)
331     {
332         return WTF::equal(str, buf.characters, buf.length);
333     }
334
335     static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
336     {
337         location = &StringImpl::create(buf.characters, buf.length).leakRef();
338         location->setHash(hash);
339         location->setIsAtomic(true);
340     }
341 };
342
343 template<typename CharType>
344 struct BufferFromStaticDataTranslator {
345     using Buffer = HashTranslatorCharBuffer<CharType>;
346     static unsigned hash(const Buffer& buf)
347     {
348         return buf.hash;
349     }
350
351     static bool equal(StringImpl* const& str, const Buffer& buf)
352     {
353         return WTF::equal(str, buf.characters, buf.length);
354     }
355
356     static void translate(StringImpl*& location, const Buffer& buf, unsigned hash)
357     {
358         location = &StringImpl::createWithoutCopying(buf.characters, buf.length).leakRef();
359         location->setHash(hash);
360         location->setIsAtomic(true);
361     }
362 };
363
364 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* characters, unsigned length)
365 {
366     if (!characters)
367         return nullptr;
368
369     if (!length)
370         return static_cast<AtomicStringImpl*>(StringImpl::empty());
371
372     LCharBuffer buffer { characters, length };
373     return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
374 }
375
376 Ref<AtomicStringImpl> AtomicStringImpl::addLiteral(const char* characters, unsigned length)
377 {
378     ASSERT(characters);
379     ASSERT(length);
380
381     LCharBuffer buffer { reinterpret_cast<const LChar*>(characters), length };
382     return addToStringTable<LCharBuffer, BufferFromStaticDataTranslator<LChar>>(buffer);
383 }
384
385 static Ref<AtomicStringImpl> addSymbol(AtomicStringTableLocker& locker, StringTableImpl& atomicStringTable, StringImpl& base)
386 {
387     ASSERT(base.length());
388     ASSERT(base.isSymbol());
389
390     SubstringLocation buffer = { &base, 0, base.length() };
391     if (base.is8Bit())
392         return addToStringTable<SubstringLocation, SubstringTranslator8>(locker, atomicStringTable, buffer);
393     return addToStringTable<SubstringLocation, SubstringTranslator16>(locker, atomicStringTable, buffer);
394 }
395
396 static inline Ref<AtomicStringImpl> addSymbol(StringImpl& base)
397 {
398     AtomicStringTableLocker locker;
399     return addSymbol(locker, stringTable(), base);
400 }
401
402 static Ref<AtomicStringImpl> addStatic(AtomicStringTableLocker& locker, StringTableImpl& atomicStringTable, StringImpl& base)
403 {
404     ASSERT(base.length());
405     ASSERT(base.isStatic());
406
407     if (base.is8Bit()) {
408         LCharBuffer buffer { base.characters8(), base.length(), base.hash() };
409         return addToStringTable<LCharBuffer, BufferFromStaticDataTranslator<LChar>>(locker, atomicStringTable, buffer);
410     }
411     UCharBuffer buffer { base.characters16(), base.length(), base.hash() };
412     return addToStringTable<UCharBuffer, BufferFromStaticDataTranslator<UChar>>(locker, atomicStringTable, buffer);
413 }
414
415 static inline Ref<AtomicStringImpl> addStatic(StringImpl& base)
416 {
417     AtomicStringTableLocker locker;
418     return addStatic(locker, stringTable(), base);
419 }
420
421 Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(StringImpl& string)
422 {
423     // This check is necessary for null symbols.
424     // Their length is zero, but they are not AtomicStringImpl.
425     if (!string.length())
426         return *static_cast<AtomicStringImpl*>(StringImpl::empty());
427
428     if (string.isStatic())
429         return addStatic(string);
430
431     if (string.isSymbol())
432         return addSymbol(string);
433
434     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
435
436     AtomicStringTableLocker locker;
437     auto addResult = stringTable().add(&string);
438
439     if (addResult.isNewEntry) {
440         ASSERT(*addResult.iterator == &string);
441         string.setIsAtomic(true);
442     }
443
444     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
445 }
446
447 Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(AtomicStringTable& stringTable, StringImpl& string)
448 {
449     // This check is necessary for null symbols.
450     // Their length is zero, but they are not AtomicStringImpl.
451     if (!string.length())
452         return *static_cast<AtomicStringImpl*>(StringImpl::empty());
453
454     if (string.isStatic()) {
455         AtomicStringTableLocker locker;
456         return addStatic(locker, stringTable.table(), string);
457     }
458
459     if (string.isSymbol()) {
460         AtomicStringTableLocker locker;
461         return addSymbol(locker, stringTable.table(), string);
462     }
463
464     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
465
466     AtomicStringTableLocker locker;
467     auto addResult = stringTable.table().add(&string);
468
469     if (addResult.isNewEntry) {
470         ASSERT(*addResult.iterator == &string);
471         string.setIsAtomic(true);
472     }
473
474     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
475 }
476
477 void AtomicStringImpl::remove(AtomicStringImpl* string)
478 {
479     ASSERT(string->isAtomic());
480     AtomicStringTableLocker locker;
481     auto& atomicStringTable = stringTable();
482     auto iterator = atomicStringTable.find(string);
483     ASSERT_WITH_MESSAGE(iterator != atomicStringTable.end(), "The string being removed is atomic in the string table of an other thread!");
484     ASSERT(string == *iterator);
485     atomicStringTable.remove(iterator);
486 }
487
488 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpSlowCase(StringImpl& string)
489 {
490     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpls should return from the fast case.");
491
492     if (!string.length())
493         return static_cast<AtomicStringImpl*>(StringImpl::empty());
494
495     AtomicStringTableLocker locker;
496     auto& atomicStringTable = stringTable();
497     auto iterator = atomicStringTable.find(&string);
498     if (iterator != atomicStringTable.end())
499         return static_cast<AtomicStringImpl*>(*iterator);
500     return nullptr;
501 }
502
503 RefPtr<AtomicStringImpl> AtomicStringImpl::addUTF8(const char* charactersStart, const char* charactersEnd)
504 {
505     HashAndUTF8Characters buffer;
506     buffer.characters = charactersStart;
507     buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
508
509     if (!buffer.hash)
510         return nullptr;
511
512     return addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
513 }
514
515 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUp(const LChar* characters, unsigned length)
516 {
517     AtomicStringTableLocker locker;
518     auto& table = stringTable();
519
520     LCharBuffer buffer = { characters, length };
521     auto iterator = table.find<LCharBufferTranslator>(buffer);
522     if (iterator != table.end())
523         return static_cast<AtomicStringImpl*>(*iterator);
524     return nullptr;
525 }
526
527 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUp(const UChar* characters, unsigned length)
528 {
529     AtomicStringTableLocker locker;
530     auto& table = stringTable();
531
532     UCharBuffer buffer { characters, length };
533     auto iterator = table.find<UCharBufferTranslator>(buffer);
534     if (iterator != table.end())
535         return static_cast<AtomicStringImpl*>(*iterator);
536     return nullptr;
537 }
538
539 #if !ASSERT_DISABLED
540 bool AtomicStringImpl::isInAtomicStringTable(StringImpl* string)
541 {
542     AtomicStringTableLocker locker;
543     return stringTable().contains(string);
544 }
545 #endif
546
547 } // namespace WTF