c836fa2e2dfa99c64678b396864e7cec42fdbf3e
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSString.cpp
1 /*
2  *  Copyright (C) 1999-2002 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
4  *  Copyright (C) 2004-2017 Apple 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 #include "config.h"
24 #include "JSString.h"
25
26 #include "JSGlobalObject.h"
27 #include "JSGlobalObjectFunctions.h"
28 #include "JSObject.h"
29 #include "JSCInlines.h"
30 #include "StringObject.h"
31 #include "StringPrototype.h"
32 #include "StrongInlines.h"
33
34 namespace JSC {
35     
36 const ClassInfo JSString::s_info = { "string", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSString) };
37
38 Structure* JSString::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue proto)
39 {
40     return Structure::create(vm, globalObject, proto, TypeInfo(StringType, StructureFlags), info());
41 }
42
43 JSString* JSString::createEmptyString(VM& vm)
44 {
45     JSString* newString = new (NotNull, allocateCell<JSString>(vm.heap)) JSString(vm, *StringImpl::empty());
46     newString->finishCreation(vm);
47     return newString;
48 }
49
50 template<>
51 void JSRopeString::RopeBuilder<RecordOverflow>::expand()
52 {
53     RELEASE_ASSERT(!this->hasOverflowed());
54     ASSERT(m_strings.size() == JSRopeString::s_maxInternalRopeLength);
55     static_assert(3 == JSRopeString::s_maxInternalRopeLength, "");
56     ASSERT(m_length);
57     ASSERT(asString(m_strings.at(0))->length());
58     ASSERT(asString(m_strings.at(1))->length());
59     ASSERT(asString(m_strings.at(2))->length());
60
61     JSString* string = JSRopeString::create(m_vm, asString(m_strings.at(0)), asString(m_strings.at(1)), asString(m_strings.at(2)));
62     ASSERT(string->length() == m_length);
63     m_strings.clear();
64     m_strings.append(string);
65 }
66
67 void JSString::destroy(JSCell* cell)
68 {
69     static_cast<JSString*>(cell)->JSString::~JSString();
70 }
71
72 void JSString::dumpToStream(const JSCell* cell, PrintStream& out)
73 {
74     VM& vm = *cell->vm();
75     const JSString* thisObject = jsCast<const JSString*>(cell);
76     out.printf("<%p, %s, [%u], ", thisObject, thisObject->className(vm), thisObject->length());
77     uintptr_t pointer = thisObject->m_fiber;
78     if (pointer & isRopeInPointer)
79         out.printf("[rope]");
80     else {
81         if (WTF::StringImpl* ourImpl = bitwise_cast<StringImpl*>(pointer)) {
82             if (ourImpl->is8Bit())
83                 out.printf("[8 %p]", ourImpl->characters8());
84             else
85                 out.printf("[16 %p]", ourImpl->characters16());
86         }
87     }
88     out.printf(">");
89 }
90
91 bool JSString::equalSlowCase(ExecState* exec, JSString* other) const
92 {
93     VM& vm = exec->vm();
94     auto scope = DECLARE_THROW_SCOPE(vm);
95     String str1 = value(exec);
96     String str2 = other->value(exec);
97     RETURN_IF_EXCEPTION(scope, false);
98     return WTF::equal(*str1.impl(), *str2.impl());
99 }
100
101 size_t JSString::estimatedSize(JSCell* cell, VM& vm)
102 {
103     JSString* thisObject = asString(cell);
104     uintptr_t pointer = thisObject->m_fiber;
105     if (pointer & isRopeInPointer)
106         return Base::estimatedSize(cell, vm);
107     return Base::estimatedSize(cell, vm) + bitwise_cast<StringImpl*>(pointer)->costDuringGC();
108 }
109
110 void JSString::visitChildren(JSCell* cell, SlotVisitor& visitor)
111 {
112     JSString* thisObject = asString(cell);
113     Base::visitChildren(thisObject, visitor);
114     
115     uintptr_t pointer = thisObject->m_fiber;
116     if (pointer & isRopeInPointer) {
117         if (pointer & JSRopeString::isSubstringInPointer) {
118             visitor.appendUnbarriered(static_cast<JSRopeString*>(thisObject)->fiber1());
119             return;
120         }
121         for (unsigned index = 0; index < JSRopeString::s_maxInternalRopeLength; ++index) {
122             JSString* fiber = nullptr;
123             switch (index) {
124             case 0:
125                 fiber = bitwise_cast<JSString*>(pointer & JSRopeString::stringMask);
126                 break;
127             case 1:
128                 fiber = static_cast<JSRopeString*>(thisObject)->fiber1();
129                 break;
130             case 2:
131                 fiber = static_cast<JSRopeString*>(thisObject)->fiber2();
132                 break;
133             default:
134                 ASSERT_NOT_REACHED();
135                 return;
136             }
137             if (!fiber)
138                 break;
139             visitor.appendUnbarriered(fiber);
140         }
141         return;
142     }
143     if (StringImpl* impl = bitwise_cast<StringImpl*>(pointer))
144         visitor.reportExtraMemoryVisited(impl->costDuringGC());
145 }
146
147 static const unsigned maxLengthForOnStackResolve = 2048;
148
149 void JSRopeString::resolveRopeInternal8(LChar* buffer) const
150 {
151     if (isSubstring()) {
152         StringImpl::copyCharacters(buffer, substringBase()->valueInternal().characters8() + substringOffset(), length());
153         return;
154     }
155     
156     resolveRopeInternal8NoSubstring(buffer);
157 }
158
159 void JSRopeString::resolveRopeInternal8NoSubstring(LChar* buffer) const
160 {
161     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
162         if (fiber(i)->isRope()) {
163             resolveRopeSlowCase8(buffer);
164             return;
165         }
166     }
167
168     LChar* position = buffer;
169     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
170         const StringImpl& fiberString = *fiber(i)->valueInternal().impl();
171         unsigned length = fiberString.length();
172         StringImpl::copyCharacters(position, fiberString.characters8(), length);
173         position += length;
174     }
175     ASSERT((buffer + length()) == position);
176 }
177
178 void JSRopeString::resolveRopeInternal16(UChar* buffer) const
179 {
180     if (isSubstring()) {
181         StringImpl::copyCharacters(
182             buffer, substringBase()->valueInternal().characters16() + substringOffset(), length());
183         return;
184     }
185     
186     resolveRopeInternal16NoSubstring(buffer);
187 }
188
189 void JSRopeString::resolveRopeInternal16NoSubstring(UChar* buffer) const
190 {
191     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
192         if (fiber(i)->isRope()) {
193             resolveRopeSlowCase(buffer);
194             return;
195         }
196     }
197
198     UChar* position = buffer;
199     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
200         const StringImpl& fiberString = *fiber(i)->valueInternal().impl();
201         unsigned length = fiberString.length();
202         if (fiberString.is8Bit())
203             StringImpl::copyCharacters(position, fiberString.characters8(), length);
204         else
205             StringImpl::copyCharacters(position, fiberString.characters16(), length);
206         position += length;
207     }
208     ASSERT((buffer + length()) == position);
209 }
210
211 AtomicString JSRopeString::resolveRopeToAtomicString(ExecState* exec) const
212 {
213     VM& vm = exec->vm();
214     auto scope = DECLARE_THROW_SCOPE(vm);
215
216     if (length() > maxLengthForOnStackResolve) {
217         scope.release();
218         return resolveRopeWithFunction(exec, [&] (Ref<StringImpl>&& newImpl) {
219             return AtomicStringImpl::add(newImpl.ptr());
220         });
221     }
222
223     if (is8Bit()) {
224         LChar buffer[maxLengthForOnStackResolve];
225         resolveRopeInternal8(buffer);
226         convertToNonRope(AtomicStringImpl::add(buffer, length()));
227     } else {
228         UChar buffer[maxLengthForOnStackResolve];
229         resolveRopeInternal16(buffer);
230         convertToNonRope(AtomicStringImpl::add(buffer, length()));
231     }
232
233     // If we resolved a string that didn't previously exist, notify the heap that we've grown.
234     if (valueInternal().impl()->hasOneRef())
235         vm.heap.reportExtraMemoryAllocated(valueInternal().impl()->cost());
236     return valueInternal();
237 }
238
239 inline void JSRopeString::convertToNonRope(String&& string) const
240 {
241     // Concurrent compiler threads can access String held by JSString. So we always emit
242     // store-store barrier here to ensure concurrent compiler threads see initialized String.
243     ASSERT(JSString::isRope());
244     WTF::storeStoreFence();
245     new (&uninitializedValueInternal()) String(WTFMove(string));
246     static_assert(sizeof(String) == sizeof(RefPtr<StringImpl>), "JSString's String initialization must be done in one pointer move.");
247     // We do not clear the trailing fibers and length information (fiber1 and fiber2) because we could be reading the length concurrently.
248     ASSERT(!JSString::isRope());
249 }
250
251 RefPtr<AtomicStringImpl> JSRopeString::resolveRopeToExistingAtomicString(ExecState* exec) const
252 {
253     VM& vm = exec->vm();
254     auto scope = DECLARE_THROW_SCOPE(vm);
255
256     if (length() > maxLengthForOnStackResolve) {
257         RefPtr<AtomicStringImpl> existingAtomicString;
258         resolveRopeWithFunction(exec, [&] (Ref<StringImpl>&& newImpl) -> Ref<StringImpl> {
259             existingAtomicString = AtomicStringImpl::lookUp(newImpl.ptr());
260             if (existingAtomicString)
261                 return makeRef(*existingAtomicString);
262             return WTFMove(newImpl);
263         });
264         RETURN_IF_EXCEPTION(scope, nullptr);
265         return existingAtomicString;
266     }
267     
268     if (is8Bit()) {
269         LChar buffer[maxLengthForOnStackResolve];
270         resolveRopeInternal8(buffer);
271         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
272             convertToNonRope(*existingAtomicString);
273             return existingAtomicString;
274         }
275     } else {
276         UChar buffer[maxLengthForOnStackResolve];
277         resolveRopeInternal16(buffer);
278         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
279             convertToNonRope(*existingAtomicString);
280             return existingAtomicString;
281         }
282     }
283
284     return nullptr;
285 }
286
287 template<typename Function>
288 const String& JSRopeString::resolveRopeWithFunction(ExecState* nullOrExecForOOM, Function&& function) const
289 {
290     ASSERT(isRope());
291     
292     VM& vm = *this->vm();
293     if (isSubstring()) {
294         ASSERT(!substringBase()->isRope());
295         auto newImpl = substringBase()->valueInternal().substringSharingImpl(substringOffset(), length());
296         convertToNonRope(function(newImpl.releaseImpl().releaseNonNull()));
297         return valueInternal();
298     }
299     
300     if (is8Bit()) {
301         LChar* buffer;
302         auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer);
303         if (!newImpl) {
304             outOfMemory(nullOrExecForOOM);
305             return nullString();
306         }
307         vm.heap.reportExtraMemoryAllocated(newImpl->cost());
308
309         resolveRopeInternal8NoSubstring(buffer);
310         convertToNonRope(function(newImpl.releaseNonNull()));
311         return valueInternal();
312     }
313     
314     UChar* buffer;
315     auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer);
316     if (!newImpl) {
317         outOfMemory(nullOrExecForOOM);
318         return nullString();
319     }
320     vm.heap.reportExtraMemoryAllocated(newImpl->cost());
321     
322     resolveRopeInternal16NoSubstring(buffer);
323     convertToNonRope(function(newImpl.releaseNonNull()));
324     return valueInternal();
325 }
326
327 const String& JSRopeString::resolveRope(ExecState* nullOrExecForOOM) const
328 {
329     return resolveRopeWithFunction(nullOrExecForOOM, [] (Ref<StringImpl>&& newImpl) {
330         return WTFMove(newImpl);
331     });
332 }
333
334 // Overview: These functions convert a JSString from holding a string in rope form
335 // down to a simple String representation. It does so by building up the string
336 // backwards, since we want to avoid recursion, we expect that the tree structure
337 // representing the rope is likely imbalanced with more nodes down the left side
338 // (since appending to the string is likely more common) - and as such resolving
339 // in this fashion should minimize work queue size.  (If we built the queue forwards
340 // we would likely have to place all of the constituent StringImpls into the
341 // Vector before performing any concatenation, but by working backwards we likely
342 // only fill the queue with the number of substrings at any given level in a
343 // rope-of-ropes.)
344 void JSRopeString::resolveRopeSlowCase8(LChar* buffer) const
345 {
346     LChar* position = buffer + length(); // We will be working backwards over the rope.
347     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // Putting strings into a Vector is only OK because there are no GC points in this method.
348     
349     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
350         workQueue.append(fiber(i));
351
352     while (!workQueue.isEmpty()) {
353         JSString* currentFiber = workQueue.last();
354         workQueue.removeLast();
355
356         const LChar* characters;
357         
358         if (currentFiber->isRope()) {
359             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
360             if (!currentFiberAsRope->isSubstring()) {
361                 for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
362                     workQueue.append(currentFiberAsRope->fiber(i));
363                 continue;
364             }
365             ASSERT(!currentFiberAsRope->substringBase()->isRope());
366             characters =
367                 currentFiberAsRope->substringBase()->valueInternal().characters8() +
368                 currentFiberAsRope->substringOffset();
369         } else
370             characters = currentFiber->valueInternal().characters8();
371         
372         unsigned length = currentFiber->length();
373         position -= length;
374         StringImpl::copyCharacters(position, characters, length);
375     }
376
377     ASSERT(buffer == position);
378 }
379
380 void JSRopeString::resolveRopeSlowCase(UChar* buffer) const
381 {
382     UChar* position = buffer + length(); // We will be working backwards over the rope.
383     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
384
385     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
386         workQueue.append(fiber(i));
387
388     while (!workQueue.isEmpty()) {
389         JSString* currentFiber = workQueue.last();
390         workQueue.removeLast();
391
392         if (currentFiber->isRope()) {
393             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
394             if (currentFiberAsRope->isSubstring()) {
395                 ASSERT(!currentFiberAsRope->substringBase()->isRope());
396                 StringImpl* string = static_cast<StringImpl*>(
397                     currentFiberAsRope->substringBase()->valueInternal().impl());
398                 unsigned offset = currentFiberAsRope->substringOffset();
399                 unsigned length = currentFiberAsRope->length();
400                 position -= length;
401                 if (string->is8Bit())
402                     StringImpl::copyCharacters(position, string->characters8() + offset, length);
403                 else
404                     StringImpl::copyCharacters(position, string->characters16() + offset, length);
405                 continue;
406             }
407             for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
408                 workQueue.append(currentFiberAsRope->fiber(i));
409             continue;
410         }
411
412         StringImpl* string = static_cast<StringImpl*>(currentFiber->valueInternal().impl());
413         unsigned length = string->length();
414         position -= length;
415         if (string->is8Bit())
416             StringImpl::copyCharacters(position, string->characters8(), length);
417         else
418             StringImpl::copyCharacters(position, string->characters16(), length);
419     }
420
421     ASSERT(buffer == position);
422 }
423
424 void JSRopeString::outOfMemory(ExecState* nullOrExecForOOM) const
425 {
426     ASSERT(isRope());
427     if (nullOrExecForOOM) {
428         VM& vm = nullOrExecForOOM->vm();
429         auto scope = DECLARE_THROW_SCOPE(vm);
430         throwOutOfMemoryError(nullOrExecForOOM, scope);
431     }
432 }
433
434 JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
435 {
436     return const_cast<JSString*>(this);
437 }
438
439 bool JSString::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
440 {
441     VM& vm = exec->vm();
442     auto scope = DECLARE_THROW_SCOPE(vm);
443     StringView view = unsafeView(exec);
444     RETURN_IF_EXCEPTION(scope, false);
445     result = this;
446     number = jsToNumber(view);
447     return false;
448 }
449
450 double JSString::toNumber(ExecState* exec) const
451 {
452     VM& vm = exec->vm();
453     auto scope = DECLARE_THROW_SCOPE(vm);
454     StringView view = unsafeView(exec);
455     RETURN_IF_EXCEPTION(scope, 0);
456     return jsToNumber(view);
457 }
458
459 inline StringObject* StringObject::create(VM& vm, JSGlobalObject* globalObject, JSString* string)
460 {
461     StringObject* object = new (NotNull, allocateCell<StringObject>(vm.heap)) StringObject(vm, globalObject->stringObjectStructure());
462     object->finishCreation(vm, string);
463     return object;
464 }
465
466 JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const
467 {
468     return StringObject::create(exec->vm(), globalObject, const_cast<JSString*>(this));
469 }
470
471 JSValue JSString::toThis(JSCell* cell, ExecState* exec, ECMAMode ecmaMode)
472 {
473     if (ecmaMode == StrictMode)
474         return cell;
475     return StringObject::create(exec->vm(), exec->lexicalGlobalObject(), asString(cell));
476 }
477
478 bool JSString::getStringPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
479 {
480     VM& vm = exec->vm();
481     if (propertyName == vm.propertyNames->length) {
482         descriptor.setDescriptor(jsNumber(length()), PropertyAttribute::DontEnum | PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
483         return true;
484     }
485     
486     Optional<uint32_t> index = parseIndex(propertyName);
487     if (index && index.value() < length()) {
488         descriptor.setDescriptor(getIndex(exec, index.value()), PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
489         return true;
490     }
491     
492     return false;
493 }
494
495 JSString* jsStringWithCacheSlowCase(VM& vm, StringImpl& stringImpl)
496 {
497     if (JSString* string = vm.stringCache.get(&stringImpl))
498         return string;
499
500     JSString* string = jsString(&vm, String(stringImpl));
501     vm.lastCachedString.set(vm, string);
502     return string;
503 }
504
505 } // namespace JSC