wtf/Optional.h: move-constructor and move-assignment operator should disengage the...
[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 template<>
44 void JSRopeString::RopeBuilder<RecordOverflow>::expand()
45 {
46     RELEASE_ASSERT(!this->hasOverflowed());
47     ASSERT(m_index == JSRopeString::s_maxInternalRopeLength);
48     JSString* jsString = m_jsString;
49     m_jsString = jsStringBuilder(&m_vm);
50     m_index = 0;
51     append(jsString);
52 }
53
54 void JSString::destroy(JSCell* cell)
55 {
56     static_cast<JSString*>(cell)->JSString::~JSString();
57 }
58
59 void JSString::dumpToStream(const JSCell* cell, PrintStream& out)
60 {
61     VM& vm = *cell->vm();
62     const JSString* thisObject = jsCast<const JSString*>(cell);
63     out.printf("<%p, %s, [%u], ", thisObject, thisObject->className(vm), thisObject->length());
64     if (thisObject->isRope())
65         out.printf("[rope]");
66     else {
67         WTF::StringImpl* ourImpl = thisObject->m_value.impl();
68         if (ourImpl->is8Bit())
69             out.printf("[8 %p]", ourImpl->characters8());
70         else
71             out.printf("[16 %p]", ourImpl->characters16());
72     }
73     out.printf(">");
74 }
75
76 bool JSString::equalSlowCase(ExecState* exec, JSString* other) const
77 {
78     VM& vm = exec->vm();
79     auto scope = DECLARE_THROW_SCOPE(vm);
80     String str1 = value(exec);
81     String str2 = other->value(exec);
82     RETURN_IF_EXCEPTION(scope, false);
83     return WTF::equal(*str1.impl(), *str2.impl());
84 }
85
86 size_t JSString::estimatedSize(JSCell* cell, VM& vm)
87 {
88     JSString* thisObject = asString(cell);
89     if (thisObject->isRope())
90         return Base::estimatedSize(cell, vm);
91     return Base::estimatedSize(cell, vm) + thisObject->m_value.impl()->costDuringGC();
92 }
93
94 void JSString::visitChildren(JSCell* cell, SlotVisitor& visitor)
95 {
96     JSString* thisObject = asString(cell);
97     Base::visitChildren(thisObject, visitor);
98     
99     if (thisObject->isRope())
100         static_cast<JSRopeString*>(thisObject)->visitFibers(visitor);
101     if (StringImpl* impl = thisObject->m_value.impl())
102         visitor.reportExtraMemoryVisited(impl->costDuringGC());
103 }
104
105 void JSRopeString::visitFibers(SlotVisitor& visitor)
106 {
107     if (isSubstring()) {
108         visitor.append(substringBase());
109         return;
110     }
111     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
112         visitor.append(fiber(i));
113 }
114
115 static const unsigned maxLengthForOnStackResolve = 2048;
116
117 void JSRopeString::resolveRopeInternal8(LChar* buffer) const
118 {
119     if (isSubstring()) {
120         StringImpl::copyCharacters(buffer, substringBase()->m_value.characters8() + substringOffset(), length());
121         return;
122     }
123     
124     resolveRopeInternal8NoSubstring(buffer);
125 }
126
127 void JSRopeString::resolveRopeInternal8NoSubstring(LChar* buffer) const
128 {
129     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
130         if (fiber(i)->isRope()) {
131             resolveRopeSlowCase8(buffer);
132             return;
133         }
134     }
135
136     LChar* position = buffer;
137     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
138         const StringImpl& fiberString = *fiber(i)->m_value.impl();
139         unsigned length = fiberString.length();
140         StringImpl::copyCharacters(position, fiberString.characters8(), length);
141         position += length;
142     }
143     ASSERT((buffer + length()) == position);
144 }
145
146 void JSRopeString::resolveRopeInternal16(UChar* buffer) const
147 {
148     if (isSubstring()) {
149         StringImpl::copyCharacters(
150             buffer, substringBase()->m_value.characters16() + substringOffset(), length());
151         return;
152     }
153     
154     resolveRopeInternal16NoSubstring(buffer);
155 }
156
157 void JSRopeString::resolveRopeInternal16NoSubstring(UChar* buffer) const
158 {
159     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
160         if (fiber(i)->isRope()) {
161             resolveRopeSlowCase(buffer);
162             return;
163         }
164     }
165
166     UChar* position = buffer;
167     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
168         const StringImpl& fiberString = *fiber(i)->m_value.impl();
169         unsigned length = fiberString.length();
170         if (fiberString.is8Bit())
171             StringImpl::copyCharacters(position, fiberString.characters8(), length);
172         else
173             StringImpl::copyCharacters(position, fiberString.characters16(), length);
174         position += length;
175     }
176     ASSERT((buffer + length()) == position);
177 }
178
179 void JSRopeString::resolveRopeToAtomicString(ExecState* exec) const
180 {
181     VM& vm = exec->vm();
182     auto scope = DECLARE_THROW_SCOPE(vm);
183
184     if (length() > maxLengthForOnStackResolve) {
185         resolveRope(exec);
186         RETURN_IF_EXCEPTION(scope, void());
187         m_value = AtomicString(m_value);
188         setIs8Bit(m_value.impl()->is8Bit());
189         return;
190     }
191
192     if (is8Bit()) {
193         LChar buffer[maxLengthForOnStackResolve];
194         resolveRopeInternal8(buffer);
195         m_value = AtomicString(buffer, length());
196         setIs8Bit(m_value.impl()->is8Bit());
197     } else {
198         UChar buffer[maxLengthForOnStackResolve];
199         resolveRopeInternal16(buffer);
200         m_value = AtomicString(buffer, length());
201         setIs8Bit(m_value.impl()->is8Bit());
202     }
203
204     clearFibers();
205
206     // If we resolved a string that didn't previously exist, notify the heap that we've grown.
207     if (m_value.impl()->hasOneRef())
208         vm.heap.reportExtraMemoryAllocated(m_value.impl()->cost());
209 }
210
211 void JSRopeString::clearFibers() const
212 {
213     for (size_t i = 0; i < s_maxInternalRopeLength; ++i)
214         u[i].number = 0;
215 }
216
217 RefPtr<AtomicStringImpl> JSRopeString::resolveRopeToExistingAtomicString(ExecState* exec) const
218 {
219     if (length() > maxLengthForOnStackResolve) {
220         resolveRope(exec);
221         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(m_value.impl())) {
222             m_value = *existingAtomicString;
223             setIs8Bit(m_value.impl()->is8Bit());
224             clearFibers();
225             return existingAtomicString;
226         }
227         return nullptr;
228     }
229     
230     if (is8Bit()) {
231         LChar buffer[maxLengthForOnStackResolve];
232         resolveRopeInternal8(buffer);
233         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
234             m_value = *existingAtomicString;
235             setIs8Bit(m_value.impl()->is8Bit());
236             clearFibers();
237             return existingAtomicString;
238         }
239     } else {
240         UChar buffer[maxLengthForOnStackResolve];
241         resolveRopeInternal16(buffer);
242         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
243             m_value = *existingAtomicString;
244             setIs8Bit(m_value.impl()->is8Bit());
245             clearFibers();
246             return existingAtomicString;
247         }
248     }
249
250     return nullptr;
251 }
252
253 void JSRopeString::resolveRope(ExecState* nullOrExecForOOM) const
254 {
255     ASSERT(isRope());
256     
257     if (isSubstring()) {
258         ASSERT(!substringBase()->isRope());
259         m_value = substringBase()->m_value.substringSharingImpl(substringOffset(), length());
260         substringBase().clear();
261         return;
262     }
263     
264     if (is8Bit()) {
265         LChar* buffer;
266         if (auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer)) {
267             Heap::heap(this)->reportExtraMemoryAllocated(newImpl->cost());
268             m_value = WTFMove(newImpl);
269         } else {
270             outOfMemory(nullOrExecForOOM);
271             return;
272         }
273         resolveRopeInternal8NoSubstring(buffer);
274         clearFibers();
275         ASSERT(!isRope());
276         return;
277     }
278     
279     UChar* buffer;
280     if (auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer)) {
281         Heap::heap(this)->reportExtraMemoryAllocated(newImpl->cost());
282         m_value = WTFMove(newImpl);
283     } else {
284         outOfMemory(nullOrExecForOOM);
285         return;
286     }
287     
288     resolveRopeInternal16NoSubstring(buffer);
289     clearFibers();
290     ASSERT(!isRope());
291 }
292
293 // Overview: These functions convert a JSString from holding a string in rope form
294 // down to a simple String representation. It does so by building up the string
295 // backwards, since we want to avoid recursion, we expect that the tree structure
296 // representing the rope is likely imbalanced with more nodes down the left side
297 // (since appending to the string is likely more common) - and as such resolving
298 // in this fashion should minimize work queue size.  (If we built the queue forwards
299 // we would likely have to place all of the constituent StringImpls into the
300 // Vector before performing any concatenation, but by working backwards we likely
301 // only fill the queue with the number of substrings at any given level in a
302 // rope-of-ropes.)
303 void JSRopeString::resolveRopeSlowCase8(LChar* buffer) const
304 {
305     LChar* position = buffer + length(); // We will be working backwards over the rope.
306     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // Putting strings into a Vector is only OK because there are no GC points in this method.
307     
308     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
309         workQueue.append(fiber(i).get());
310
311     while (!workQueue.isEmpty()) {
312         JSString* currentFiber = workQueue.last();
313         workQueue.removeLast();
314
315         const LChar* characters;
316         
317         if (currentFiber->isRope()) {
318             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
319             if (!currentFiberAsRope->isSubstring()) {
320                 for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
321                     workQueue.append(currentFiberAsRope->fiber(i).get());
322                 continue;
323             }
324             ASSERT(!currentFiberAsRope->substringBase()->isRope());
325             characters =
326                 currentFiberAsRope->substringBase()->m_value.characters8() +
327                 currentFiberAsRope->substringOffset();
328         } else
329             characters = currentFiber->m_value.characters8();
330         
331         unsigned length = currentFiber->length();
332         position -= length;
333         StringImpl::copyCharacters(position, characters, length);
334     }
335
336     ASSERT(buffer == position);
337 }
338
339 void JSRopeString::resolveRopeSlowCase(UChar* buffer) const
340 {
341     UChar* position = buffer + length(); // We will be working backwards over the rope.
342     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
343
344     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
345         workQueue.append(fiber(i).get());
346
347     while (!workQueue.isEmpty()) {
348         JSString* currentFiber = workQueue.last();
349         workQueue.removeLast();
350
351         if (currentFiber->isRope()) {
352             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
353             if (currentFiberAsRope->isSubstring()) {
354                 ASSERT(!currentFiberAsRope->substringBase()->isRope());
355                 StringImpl* string = static_cast<StringImpl*>(
356                     currentFiberAsRope->substringBase()->m_value.impl());
357                 unsigned offset = currentFiberAsRope->substringOffset();
358                 unsigned length = currentFiberAsRope->length();
359                 position -= length;
360                 if (string->is8Bit())
361                     StringImpl::copyCharacters(position, string->characters8() + offset, length);
362                 else
363                     StringImpl::copyCharacters(position, string->characters16() + offset, length);
364                 continue;
365             }
366             for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
367                 workQueue.append(currentFiberAsRope->fiber(i).get());
368             continue;
369         }
370
371         StringImpl* string = static_cast<StringImpl*>(currentFiber->m_value.impl());
372         unsigned length = string->length();
373         position -= length;
374         if (string->is8Bit())
375             StringImpl::copyCharacters(position, string->characters8(), length);
376         else
377             StringImpl::copyCharacters(position, string->characters16(), length);
378     }
379
380     ASSERT(buffer == position);
381 }
382
383 void JSRopeString::outOfMemory(ExecState* nullOrExecForOOM) const
384 {
385     clearFibers();
386     ASSERT(isRope());
387     ASSERT(m_value.isNull());
388     if (nullOrExecForOOM) {
389         VM& vm = nullOrExecForOOM->vm();
390         auto scope = DECLARE_THROW_SCOPE(vm);
391         throwOutOfMemoryError(nullOrExecForOOM, scope);
392     }
393 }
394
395 JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
396 {
397     return const_cast<JSString*>(this);
398 }
399
400 bool JSString::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
401 {
402     VM& vm = exec->vm();
403     auto scope = DECLARE_THROW_SCOPE(vm);
404     StringView view = unsafeView(exec);
405     RETURN_IF_EXCEPTION(scope, false);
406     result = this;
407     number = jsToNumber(view);
408     return false;
409 }
410
411 double JSString::toNumber(ExecState* exec) const
412 {
413     VM& vm = exec->vm();
414     auto scope = DECLARE_THROW_SCOPE(vm);
415     StringView view = unsafeView(exec);
416     RETURN_IF_EXCEPTION(scope, 0);
417     return jsToNumber(view);
418 }
419
420 inline StringObject* StringObject::create(VM& vm, JSGlobalObject* globalObject, JSString* string)
421 {
422     StringObject* object = new (NotNull, allocateCell<StringObject>(vm.heap)) StringObject(vm, globalObject->stringObjectStructure());
423     object->finishCreation(vm, string);
424     return object;
425 }
426
427 JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const
428 {
429     return StringObject::create(exec->vm(), globalObject, const_cast<JSString*>(this));
430 }
431
432 JSValue JSString::toThis(JSCell* cell, ExecState* exec, ECMAMode ecmaMode)
433 {
434     if (ecmaMode == StrictMode)
435         return cell;
436     return StringObject::create(exec->vm(), exec->lexicalGlobalObject(), asString(cell));
437 }
438
439 bool JSString::getStringPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
440 {
441     VM& vm = exec->vm();
442     if (propertyName == vm.propertyNames->length) {
443         descriptor.setDescriptor(jsNumber(length()), PropertyAttribute::DontEnum | PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
444         return true;
445     }
446     
447     Optional<uint32_t> index = parseIndex(propertyName);
448     if (index && index.value() < length()) {
449         descriptor.setDescriptor(getIndex(exec, index.value()), PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
450         return true;
451     }
452     
453     return false;
454 }
455
456 JSString* jsStringWithCacheSlowCase(VM& vm, StringImpl& stringImpl)
457 {
458     if (JSString* string = vm.stringCache.get(&stringImpl))
459         return string;
460
461     JSString* string = jsString(&vm, String(stringImpl));
462     vm.lastCachedString.set(vm, string);
463     return string;
464 }
465
466 } // namespace JSC