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