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
34namespace JSC {
35
36const ClassInfo JSString::s_info = { "string", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSString) };
37
38Structure* JSString::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue proto)
39{
40 return Structure::create(vm, globalObject, proto, TypeInfo(StringType, StructureFlags), info());
41}
42
43JSString* 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
50template<>
51void 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
67void JSString::destroy(JSCell* cell)
68{
69 static_cast<JSString*>(cell)->JSString::~JSString();
70}
71
72void 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
94bool 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
104size_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
113void 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
150static const unsigned maxLengthForOnStackResolve = 2048;
151
152void 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
162void 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
181void 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
192void 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
214AtomicString 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
242inline 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
254RefPtr<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
290template<typename Function>
291const 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
330const 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.)
347void 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
383void 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
427void 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
437JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
438{
439 return const_cast<JSString*>(this);
440}
441
442bool 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
453double 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
462inline 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
469JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const
470{
471 return StringObject::create(exec->vm(), globalObject, const_cast<JSString*>(this));
472}
473
474JSValue 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
481bool 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
498JSString* 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
509