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