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