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