34813a2ed33e6cfc0311c8cf9106b68c521d3adc
[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     if (length() > maxLengthForOnStackResolve) {
182         resolveRope(exec);
183         m_value = AtomicString(m_value);
184         setIs8Bit(m_value.impl()->is8Bit());
185         return;
186     }
187
188     if (is8Bit()) {
189         LChar buffer[maxLengthForOnStackResolve];
190         resolveRopeInternal8(buffer);
191         m_value = AtomicString(buffer, length());
192         setIs8Bit(m_value.impl()->is8Bit());
193     } else {
194         UChar buffer[maxLengthForOnStackResolve];
195         resolveRopeInternal16(buffer);
196         m_value = AtomicString(buffer, length());
197         setIs8Bit(m_value.impl()->is8Bit());
198     }
199
200     clearFibers();
201
202     // If we resolved a string that didn't previously exist, notify the heap that we've grown.
203     if (m_value.impl()->hasOneRef())
204         Heap::heap(this)->reportExtraMemoryAllocated(m_value.impl()->cost());
205 }
206
207 void JSRopeString::clearFibers() const
208 {
209     for (size_t i = 0; i < s_maxInternalRopeLength; ++i)
210         u[i].number = 0;
211 }
212
213 RefPtr<AtomicStringImpl> JSRopeString::resolveRopeToExistingAtomicString(ExecState* exec) const
214 {
215     if (length() > maxLengthForOnStackResolve) {
216         resolveRope(exec);
217         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(m_value.impl())) {
218             m_value = *existingAtomicString;
219             setIs8Bit(m_value.impl()->is8Bit());
220             clearFibers();
221             return existingAtomicString;
222         }
223         return nullptr;
224     }
225     
226     if (is8Bit()) {
227         LChar buffer[maxLengthForOnStackResolve];
228         resolveRopeInternal8(buffer);
229         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
230             m_value = *existingAtomicString;
231             setIs8Bit(m_value.impl()->is8Bit());
232             clearFibers();
233             return existingAtomicString;
234         }
235     } else {
236         UChar buffer[maxLengthForOnStackResolve];
237         resolveRopeInternal16(buffer);
238         if (RefPtr<AtomicStringImpl> existingAtomicString = AtomicStringImpl::lookUp(buffer, length())) {
239             m_value = *existingAtomicString;
240             setIs8Bit(m_value.impl()->is8Bit());
241             clearFibers();
242             return existingAtomicString;
243         }
244     }
245
246     return nullptr;
247 }
248
249 void JSRopeString::resolveRope(ExecState* exec) const
250 {
251     ASSERT(isRope());
252     
253     if (isSubstring()) {
254         ASSERT(!substringBase()->isRope());
255         m_value = substringBase()->m_value.substringSharingImpl(substringOffset(), length());
256         substringBase().clear();
257         return;
258     }
259     
260     if (is8Bit()) {
261         LChar* buffer;
262         if (auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer)) {
263             Heap::heap(this)->reportExtraMemoryAllocated(newImpl->cost());
264             m_value = WTFMove(newImpl);
265         } else {
266             outOfMemory(exec);
267             return;
268         }
269         resolveRopeInternal8NoSubstring(buffer);
270         clearFibers();
271         ASSERT(!isRope());
272         return;
273     }
274
275     UChar* buffer;
276     if (auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer)) {
277         Heap::heap(this)->reportExtraMemoryAllocated(newImpl->cost());
278         m_value = WTFMove(newImpl);
279     } else {
280         outOfMemory(exec);
281         return;
282     }
283
284     resolveRopeInternal16NoSubstring(buffer);
285     clearFibers();
286     ASSERT(!isRope());
287 }
288
289 // Overview: These functions convert a JSString from holding a string in rope form
290 // down to a simple String representation. It does so by building up the string
291 // backwards, since we want to avoid recursion, we expect that the tree structure
292 // representing the rope is likely imbalanced with more nodes down the left side
293 // (since appending to the string is likely more common) - and as such resolving
294 // in this fashion should minimize work queue size.  (If we built the queue forwards
295 // we would likely have to place all of the constituent StringImpls into the
296 // Vector before performing any concatenation, but by working backwards we likely
297 // only fill the queue with the number of substrings at any given level in a
298 // rope-of-ropes.)    
299 void JSRopeString::resolveRopeSlowCase8(LChar* buffer) const
300 {
301     LChar* position = buffer + length(); // We will be working backwards over the rope.
302     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // Putting strings into a Vector is only OK because there are no GC points in this method.
303     
304     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
305         workQueue.append(fiber(i).get());
306
307     while (!workQueue.isEmpty()) {
308         JSString* currentFiber = workQueue.last();
309         workQueue.removeLast();
310
311         const LChar* characters;
312         
313         if (currentFiber->isRope()) {
314             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
315             if (!currentFiberAsRope->isSubstring()) {
316                 for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
317                     workQueue.append(currentFiberAsRope->fiber(i).get());
318                 continue;
319             }
320             ASSERT(!currentFiberAsRope->substringBase()->isRope());
321             characters =
322                 currentFiberAsRope->substringBase()->m_value.characters8() +
323                 currentFiberAsRope->substringOffset();
324         } else
325             characters = currentFiber->m_value.characters8();
326         
327         unsigned length = currentFiber->length();
328         position -= length;
329         StringImpl::copyChars(position, characters, length);
330     }
331
332     ASSERT(buffer == position);
333 }
334
335 void JSRopeString::resolveRopeSlowCase(UChar* buffer) const
336 {
337     UChar* position = buffer + length(); // We will be working backwards over the rope.
338     Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
339
340     for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
341         workQueue.append(fiber(i).get());
342
343     while (!workQueue.isEmpty()) {
344         JSString* currentFiber = workQueue.last();
345         workQueue.removeLast();
346
347         if (currentFiber->isRope()) {
348             JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
349             if (currentFiberAsRope->isSubstring()) {
350                 ASSERT(!currentFiberAsRope->substringBase()->isRope());
351                 StringImpl* string = static_cast<StringImpl*>(
352                     currentFiberAsRope->substringBase()->m_value.impl());
353                 unsigned offset = currentFiberAsRope->substringOffset();
354                 unsigned length = currentFiberAsRope->length();
355                 position -= length;
356                 if (string->is8Bit())
357                     StringImpl::copyChars(position, string->characters8() + offset, length);
358                 else
359                     StringImpl::copyChars(position, string->characters16() + offset, length);
360                 continue;
361             }
362             for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
363                 workQueue.append(currentFiberAsRope->fiber(i).get());
364             continue;
365         }
366
367         StringImpl* string = static_cast<StringImpl*>(currentFiber->m_value.impl());
368         unsigned length = string->length();
369         position -= length;
370         if (string->is8Bit())
371             StringImpl::copyChars(position, string->characters8(), length);
372         else
373             StringImpl::copyChars(position, string->characters16(), length);
374     }
375
376     ASSERT(buffer == position);
377 }
378
379 void JSRopeString::outOfMemory(ExecState* exec) const
380 {
381     VM& vm = exec->vm();
382     auto scope = DECLARE_THROW_SCOPE(vm);
383
384     clearFibers();
385     ASSERT(isRope());
386     ASSERT(m_value.isNull());
387     if (exec)
388         throwOutOfMemoryError(exec, scope);
389 }
390
391 JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
392 {
393     return const_cast<JSString*>(this);
394 }
395
396 bool JSString::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
397 {
398     VM& vm = exec->vm();
399     auto scope = DECLARE_THROW_SCOPE(vm);
400     StringView view = unsafeView(exec);
401     RETURN_IF_EXCEPTION(scope, false);
402     result = this;
403     number = jsToNumber(view);
404     return false;
405 }
406
407 double JSString::toNumber(ExecState* exec) const
408 {
409     VM& vm = exec->vm();
410     auto scope = DECLARE_THROW_SCOPE(vm);
411     StringView view = unsafeView(exec);
412     RETURN_IF_EXCEPTION(scope, 0);
413     return jsToNumber(view);
414 }
415
416 inline StringObject* StringObject::create(VM& vm, JSGlobalObject* globalObject, JSString* string)
417 {
418     StringObject* object = new (NotNull, allocateCell<StringObject>(vm.heap)) StringObject(vm, globalObject->stringObjectStructure());
419     object->finishCreation(vm, string);
420     return object;
421 }
422
423 JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const
424 {
425     return StringObject::create(exec->vm(), globalObject, const_cast<JSString*>(this));
426 }
427
428 JSValue JSString::toThis(JSCell* cell, ExecState* exec, ECMAMode ecmaMode)
429 {
430     if (ecmaMode == StrictMode)
431         return cell;
432     return StringObject::create(exec->vm(), exec->lexicalGlobalObject(), asString(cell));
433 }
434
435 bool JSString::getStringPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
436 {
437     if (propertyName == exec->propertyNames().length) {
438         descriptor.setDescriptor(jsNumber(length()), DontEnum | DontDelete | ReadOnly);
439         return true;
440     }
441     
442     std::optional<uint32_t> index = parseIndex(propertyName);
443     if (index && index.value() < length()) {
444         descriptor.setDescriptor(getIndex(exec, index.value()), DontDelete | ReadOnly);
445         return true;
446     }
447     
448     return false;
449 }
450
451 JSString* jsStringWithCacheSlowCase(VM& vm, StringImpl& stringImpl)
452 {
453     if (JSString* string = vm.stringCache.get(&stringImpl))
454         return string;
455
456     JSString* string = jsString(&vm, String(stringImpl));
457     vm.lastCachedString.set(vm, string);
458     return string;
459 }
460
461 } // namespace JSC