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