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