af7ccb56336201a199909f4b17ca3f216083979e
[WebKit-https.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 static ALWAYS_INLINE HashSet<StringImpl*>& stringTable()
72 {
73     return wtfThreadData().atomicStringTable()->table();
74 }
75
76 template<typename T, typename HashTranslator>
77 static inline Ref<AtomicStringImpl> addToStringTable(const T& value)
78 {
79     AtomicStringTableLocker locker;
80
81     HashSet<StringImpl*>& atomicStringTable = stringTable();
82     HashSet<StringImpl*>::AddResult addResult = atomicStringTable.add<HashTranslator>(value);
83
84     // If the string is newly-translated, then we need to adopt it.
85     // The boolean in the pair tells us if that is so.
86     if (addResult.isNewEntry)
87         return adoptRef(static_cast<AtomicStringImpl&>(**addResult.iterator));
88     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
89 }
90
91 struct CStringTranslator {
92     static unsigned hash(const LChar* c)
93     {
94         return StringHasher::computeHashAndMaskTop8Bits(c);
95     }
96
97     static inline bool equal(StringImpl* r, const LChar* s)
98     {
99         return WTF::equal(r, s);
100     }
101
102     static void translate(StringImpl*& location, const LChar* const& c, unsigned hash)
103     {
104         location = &StringImpl::create(c).leakRef();
105         location->setHash(hash);
106         location->setIsAtomic(true);
107     }
108 };
109
110 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* c)
111 {
112     if (!c)
113         return nullptr;
114     if (!*c)
115         return static_cast<AtomicStringImpl*>(StringImpl::empty());
116
117     return addToStringTable<const LChar*, CStringTranslator>(c);
118 }
119
120 template<typename CharacterType>
121 struct HashTranslatorCharBuffer {
122     const CharacterType* s;
123     unsigned length;
124 };
125
126 typedef HashTranslatorCharBuffer<UChar> UCharBuffer;
127 struct UCharBufferTranslator {
128     static unsigned hash(const UCharBuffer& buf)
129     {
130         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
131     }
132
133     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
134     {
135         return WTF::equal(str, buf.s, buf.length);
136     }
137
138     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
139     {
140         location = &StringImpl::create8BitIfPossible(buf.s, buf.length).leakRef();
141         location->setHash(hash);
142         location->setIsAtomic(true);
143     }
144 };
145
146 template<typename CharacterType>
147 struct HashAndCharacters {
148     unsigned hash;
149     const CharacterType* characters;
150     unsigned length;
151 };
152
153 template<typename CharacterType>
154 struct HashAndCharactersTranslator {
155     static unsigned hash(const HashAndCharacters<CharacterType>& buffer)
156     {
157         ASSERT(buffer.hash == StringHasher::computeHashAndMaskTop8Bits(buffer.characters, buffer.length));
158         return buffer.hash;
159     }
160
161     static bool equal(StringImpl* const& string, const HashAndCharacters<CharacterType>& buffer)
162     {
163         return WTF::equal(string, buffer.characters, buffer.length);
164     }
165
166     static void translate(StringImpl*& location, const HashAndCharacters<CharacterType>& buffer, unsigned hash)
167     {
168         location = &StringImpl::create(buffer.characters, buffer.length).leakRef();
169         location->setHash(hash);
170         location->setIsAtomic(true);
171     }
172 };
173
174 struct HashAndUTF8Characters {
175     unsigned hash;
176     const char* characters;
177     unsigned length;
178     unsigned utf16Length;
179 };
180
181 struct HashAndUTF8CharactersTranslator {
182     static unsigned hash(const HashAndUTF8Characters& buffer)
183     {
184         return buffer.hash;
185     }
186
187     static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
188     {
189         if (buffer.utf16Length != string->length())
190             return false;
191
192         // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
193         if (buffer.utf16Length != buffer.length) {
194             if (string->is8Bit())
195                 return equalLatin1WithUTF8(string->characters8(), buffer.characters, buffer.characters + buffer.length);
196
197             return equalUTF16WithUTF8(string->characters16(), buffer.characters, buffer.characters + buffer.length);
198         }
199
200         if (string->is8Bit()) {
201             const LChar* stringCharacters = string->characters8();
202
203             for (unsigned i = 0; i < buffer.length; ++i) {
204                 ASSERT(isASCII(buffer.characters[i]));
205                 if (stringCharacters[i] != buffer.characters[i])
206                     return false;
207             }
208
209             return true;
210         }
211
212         const UChar* stringCharacters = string->characters16();
213
214         for (unsigned i = 0; i < buffer.length; ++i) {
215             ASSERT(isASCII(buffer.characters[i]));
216             if (stringCharacters[i] != buffer.characters[i])
217                 return false;
218         }
219
220         return true;
221     }
222
223     static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
224     {
225         UChar* target;
226         auto newString = StringImpl::createUninitialized(buffer.utf16Length, target);
227
228         bool isAllASCII;
229         const char* source = buffer.characters;
230         if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length, &isAllASCII) != conversionOK)
231             ASSERT_NOT_REACHED();
232
233         if (isAllASCII)
234             newString = StringImpl::create(buffer.characters, buffer.length);
235
236         location = &newString.leakRef();
237         location->setHash(hash);
238         location->setIsAtomic(true);
239     }
240 };
241
242 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* s, unsigned length)
243 {
244     if (!s)
245         return nullptr;
246
247     if (!length)
248         return static_cast<AtomicStringImpl*>(StringImpl::empty());
249
250     UCharBuffer buffer = { s, length };
251     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
252 }
253
254 Ref<AtomicStringImpl> AtomicStringImpl::add(const UChar* s, unsigned length, unsigned existingHash)
255 {
256     ASSERT(s);
257     ASSERT(existingHash);
258
259     if (!length)
260         return *static_cast<AtomicStringImpl*>(StringImpl::empty());
261
262     HashAndCharacters<UChar> buffer = { existingHash, s, length };
263     return addToStringTable<HashAndCharacters<UChar>, HashAndCharactersTranslator<UChar>>(buffer);
264 }
265
266 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* s)
267 {
268     if (!s)
269         return nullptr;
270
271     unsigned length = 0;
272     while (s[length] != UChar(0))
273         ++length;
274
275     if (!length)
276         return static_cast<AtomicStringImpl*>(StringImpl::empty());
277
278     UCharBuffer buffer = { s, length };
279     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
280 }
281
282 struct SubstringLocation {
283     StringImpl* baseString;
284     unsigned start;
285     unsigned length;
286 };
287
288 struct SubstringTranslator {
289     static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
290     {
291         location = &StringImpl::createSubstringSharingImpl(*buffer.baseString, buffer.start, buffer.length).leakRef();
292         location->setHash(hash);
293         location->setIsAtomic(true);
294     }
295 };
296
297 struct SubstringTranslator8 : SubstringTranslator {
298     static unsigned hash(const SubstringLocation& buffer)
299     {
300         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters8() + buffer.start, buffer.length);
301     }
302
303     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
304     {
305         return WTF::equal(string, buffer.baseString->characters8() + buffer.start, buffer.length);
306     }
307 };
308
309 struct SubstringTranslator16 : SubstringTranslator {
310     static unsigned hash(const SubstringLocation& buffer)
311     {
312         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters16() + buffer.start, buffer.length);
313     }
314
315     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
316     {
317         return WTF::equal(string, buffer.baseString->characters16() + buffer.start, buffer.length);
318     }
319 };
320
321 RefPtr<AtomicStringImpl> AtomicStringImpl::add(StringImpl* baseString, unsigned start, unsigned length)
322 {
323     if (!baseString)
324         return nullptr;
325
326     if (!length || start >= baseString->length())
327         return static_cast<AtomicStringImpl*>(StringImpl::empty());
328
329     unsigned maxLength = baseString->length() - start;
330     if (length >= maxLength) {
331         if (!start)
332             return add(baseString);
333         length = maxLength;
334     }
335
336     SubstringLocation buffer = { baseString, start, length };
337     if (baseString->is8Bit())
338         return addToStringTable<SubstringLocation, SubstringTranslator8>(buffer);
339     return addToStringTable<SubstringLocation, SubstringTranslator16>(buffer);
340 }
341     
342 typedef HashTranslatorCharBuffer<LChar> LCharBuffer;
343 struct LCharBufferTranslator {
344     static unsigned hash(const LCharBuffer& buf)
345     {
346         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
347     }
348
349     static bool equal(StringImpl* const& str, const LCharBuffer& buf)
350     {
351         return WTF::equal(str, buf.s, buf.length);
352     }
353
354     static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
355     {
356         location = &StringImpl::create(buf.s, buf.length).leakRef();
357         location->setHash(hash);
358         location->setIsAtomic(true);
359     }
360 };
361
362 typedef HashTranslatorCharBuffer<char> CharBuffer;
363 struct CharBufferFromLiteralDataTranslator {
364     static unsigned hash(const CharBuffer& buf)
365     {
366         return StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(buf.s), buf.length);
367     }
368
369     static bool equal(StringImpl* const& str, const CharBuffer& buf)
370     {
371         return WTF::equal(str, buf.s, buf.length);
372     }
373
374     static void translate(StringImpl*& location, const CharBuffer& buf, unsigned hash)
375     {
376         location = &StringImpl::createFromLiteral(buf.s, buf.length).leakRef();
377         location->setHash(hash);
378         location->setIsAtomic(true);
379     }
380 };
381
382 RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* s, unsigned length)
383 {
384     if (!s)
385         return nullptr;
386
387     if (!length)
388         return static_cast<AtomicStringImpl*>(StringImpl::empty());
389
390     LCharBuffer buffer = { s, length };
391     return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
392 }
393
394 Ref<AtomicStringImpl> AtomicStringImpl::addLiteral(const char* characters, unsigned length)
395 {
396     ASSERT(characters);
397     ASSERT(length);
398
399     CharBuffer buffer = { characters, length };
400     return addToStringTable<CharBuffer, CharBufferFromLiteralDataTranslator>(buffer);
401 }
402
403 Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(StringImpl& string)
404 {
405     if (!string.length())
406         return *static_cast<AtomicStringImpl*>(StringImpl::empty());
407
408     if (string.isSymbol() || string.isStatic()) {
409         if (string.is8Bit())
410             return *add(string.characters8(), string.length());
411         return *add(string.characters16(), string.length());
412     }
413
414     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
415
416     AtomicStringTableLocker locker;
417     auto addResult = stringTable().add(&string);
418
419     if (addResult.isNewEntry) {
420         ASSERT(*addResult.iterator == &string);
421         string.setIsAtomic(true);
422     }
423
424     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
425 }
426
427 Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(AtomicStringTable& stringTable, StringImpl& string)
428 {
429     if (!string.length())
430         return *static_cast<AtomicStringImpl*>(StringImpl::empty());
431
432     if (string.isSymbol() || string.isStatic()) {
433         if (string.is8Bit())
434             return *add(string.characters8(), string.length());
435         return *add(string.characters16(), string.length());
436     }
437
438     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
439
440     AtomicStringTableLocker locker;
441     auto addResult = stringTable.table().add(&string);
442
443     if (addResult.isNewEntry) {
444         ASSERT(*addResult.iterator == &string);
445         string.setIsAtomic(true);
446     }
447
448     return *static_cast<AtomicStringImpl*>(*addResult.iterator);
449 }
450
451 void AtomicStringImpl::remove(AtomicStringImpl* string)
452 {
453     ASSERT(string->isAtomic());
454     AtomicStringTableLocker locker;
455     HashSet<StringImpl*>& atomicStringTable = stringTable();
456     HashSet<StringImpl*>::iterator iterator = atomicStringTable.find(string);
457     ASSERT_WITH_MESSAGE(iterator != atomicStringTable.end(), "The string being removed is atomic in the string table of an other thread!");
458     ASSERT(string == *iterator);
459     atomicStringTable.remove(iterator);
460 }
461
462 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpSlowCase(StringImpl& string)
463 {
464     ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpls should return from the fast case.");
465
466     if (!string.length())
467         return static_cast<AtomicStringImpl*>(StringImpl::empty());
468
469     if (string.isSymbol() || string.isStatic()) {
470         if (string.is8Bit())
471             return lookUpInternal(string.characters8(), string.length());
472         return lookUpInternal(string.characters16(), string.length());
473     }
474
475     AtomicStringTableLocker locker;
476     HashSet<StringImpl*>& atomicStringTable = stringTable();
477     auto iterator = atomicStringTable.find(&string);
478     if (iterator != atomicStringTable.end())
479         return static_cast<AtomicStringImpl*>(*iterator);
480     return nullptr;
481 }
482
483 RefPtr<AtomicStringImpl> AtomicStringImpl::addUTF8(const char* charactersStart, const char* charactersEnd)
484 {
485     HashAndUTF8Characters buffer;
486     buffer.characters = charactersStart;
487     buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
488
489     if (!buffer.hash)
490         return nullptr;
491
492     return addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
493 }
494
495 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpInternal(const LChar* characters, unsigned length)
496 {
497     AtomicStringTableLocker locker;
498     auto& table = stringTable();
499
500     LCharBuffer buffer = { characters, length };
501     auto iterator = table.find<LCharBufferTranslator>(buffer);
502     if (iterator != table.end())
503         return static_cast<AtomicStringImpl*>(*iterator);
504     return nullptr;
505 }
506
507 RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpInternal(const UChar* characters, unsigned length)
508 {
509     AtomicStringTableLocker locker;
510     auto& table = stringTable();
511
512     UCharBuffer buffer = { characters, length };
513     auto iterator = table.find<UCharBufferTranslator>(buffer);
514     if (iterator != table.end())
515         return static_cast<AtomicStringImpl*>(*iterator);
516     return nullptr;
517 }
518
519 #if !ASSERT_DISABLED
520 bool AtomicStringImpl::isInAtomicStringTable(StringImpl* string)
521 {
522     AtomicStringTableLocker locker;
523     return stringTable().contains(string);
524 }
525 #endif
526
527 } // namespace WTF