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 "Operations.h"
30#include "StringObject.h"
31#include "StringPrototype.h"
32
33namespace JSC {
34
35static const unsigned substringFromRopeCutoff = 4;
36
37const ClassInfo JSString::s_info = { "string", 0, 0, 0, CREATE_METHOD_TABLE(JSString) };
38
39void JSRopeString::RopeBuilder::expand()
40{
41    ASSERT(m_index == JSRopeString::s_maxInternalRopeLength);
42    JSString* jsString = m_jsString;
43    RELEASE_ASSERT(jsString);
44    m_jsString = jsStringBuilder(&m_vm);
45    m_index = 0;
46    append(jsString);
47}
48
49void JSString::destroy(JSCell* cell)
50{
51    JSString* thisObject = static_cast<JSString*>(cell);
52    thisObject->JSString::~JSString();
53}
54
55void JSString::visitChildren(JSCell* cell, SlotVisitor& visitor)
56{
57    JSString* thisObject = jsCast<JSString*>(cell);
58    Base::visitChildren(thisObject, visitor);
59
60    MARK_LOG_MESSAGE1("[%u]: ", thisObject->length());
61
62#if ENABLE(OBJECT_MARK_LOGGING)
63    if (!thisObject->isRope()) {
64        WTF::StringImpl* ourImpl = thisObject->m_value.impl();
65        if (ourImpl->is8Bit())
66            MARK_LOG_MESSAGE1("[8 %p]", ourImpl->characters8());
67        else
68            MARK_LOG_MESSAGE1("[16 %p]", ourImpl->characters16());
69    } else
70        MARK_LOG_MESSAGE0("[rope]: ");
71#endif
72
73    if (thisObject->isRope())
74        static_cast<JSRopeString*>(thisObject)->visitFibers(visitor);
75}
76
77void JSRopeString::visitFibers(SlotVisitor& visitor)
78{
79    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
80        visitor.append(&m_fibers[i]);
81}
82
83void JSRopeString::resolveRope(ExecState* exec) const
84{
85    ASSERT(isRope());
86
87    if (is8Bit()) {
88        LChar* buffer;
89        if (RefPtr<StringImpl> newImpl = StringImpl::tryCreateUninitialized(m_length, buffer)) {
90            Heap::heap(this)->reportExtraMemoryCost(newImpl->cost());
91            m_value = newImpl.release();
92        } else {
93            outOfMemory(exec);
94            return;
95        }
96
97        for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
98            if (m_fibers[i]->isRope())
99                return resolveRopeSlowCase8(buffer);
100        }
101
102        LChar* position = buffer;
103        for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
104            StringImpl* string = m_fibers[i]->m_value.impl();
105            unsigned length = string->length();
106            StringImpl::copyChars(position, string->characters8(), length);
107            position += length;
108            m_fibers[i].clear();
109        }
110        ASSERT((buffer + m_length) == position);
111        ASSERT(!isRope());
112
113        return;
114    }
115
116    UChar* buffer;
117    if (RefPtr<StringImpl> newImpl = StringImpl::tryCreateUninitialized(m_length, buffer)) {
118        Heap::heap(this)->reportExtraMemoryCost(newImpl->cost());
119        m_value = newImpl.release();
120    } else {
121        outOfMemory(exec);
122        return;
123    }
124
125    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
126        if (m_fibers[i]->isRope())
127            return resolveRopeSlowCase(buffer);
128    }
129
130    UChar* position = buffer;
131    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
132        StringImpl* string = m_fibers[i]->m_value.impl();
133        unsigned length = string->length();
134        if (string->is8Bit())
135            StringImpl::copyChars(position, string->characters8(), length);
136        else
137            StringImpl::copyChars(position, string->characters16(), length);
138        position += length;
139        m_fibers[i].clear();
140    }
141    ASSERT((buffer + m_length) == position);
142    ASSERT(!isRope());
143}
144
145// Overview: These functions convert a JSString from holding a string in rope form
146// down to a simple String representation. It does so by building up the string
147// backwards, since we want to avoid recursion, we expect that the tree structure
148// representing the rope is likely imbalanced with more nodes down the left side
149// (since appending to the string is likely more common) - and as such resolving
150// in this fashion should minimize work queue size.  (If we built the queue forwards
151// we would likely have to place all of the constituent StringImpls into the
152// Vector before performing any concatenation, but by working backwards we likely
153// only fill the queue with the number of substrings at any given level in a
154// rope-of-ropes.)
155void JSRopeString::resolveRopeSlowCase8(LChar* buffer) const
156{
157    LChar* position = buffer + m_length; // We will be working backwards over the rope.
158    Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // Putting strings into a Vector is only OK because there are no GC points in this method.
159
160    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i) {
161        workQueue.append(m_fibers[i].get());
162        // Clearing here works only because there are no GC points in this method.
163        m_fibers[i].clear();
164    }
165
166    while (!workQueue.isEmpty()) {
167        JSString* currentFiber = workQueue.last();
168        workQueue.removeLast();
169
170        if (currentFiber->isRope()) {
171            JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
172            for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->m_fibers[i]; ++i)
173                workQueue.append(currentFiberAsRope->m_fibers[i].get());
174            continue;
175        }
176
177        StringImpl* string = static_cast<StringImpl*>(currentFiber->m_value.impl());
178        unsigned length = string->length();
179        position -= length;
180        StringImpl::copyChars(position, string->characters8(), length);
181    }
182
183    ASSERT(buffer == position);
184    ASSERT(!isRope());
185}
186
187void JSRopeString::resolveRopeSlowCase(UChar* buffer) const
188{
189    UChar* position = buffer + m_length; // We will be working backwards over the rope.
190    Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
191
192    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
193        workQueue.append(m_fibers[i].get());
194
195    while (!workQueue.isEmpty()) {
196        JSString* currentFiber = workQueue.last();
197        workQueue.removeLast();
198
199        if (currentFiber->isRope()) {
200            JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
201            for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->m_fibers[i]; ++i)
202                workQueue.append(currentFiberAsRope->m_fibers[i].get());
203            continue;
204        }
205
206        StringImpl* string = static_cast<StringImpl*>(currentFiber->m_value.impl());
207        unsigned length = string->length();
208        position -= length;
209        if (string->is8Bit())
210            StringImpl::copyChars(position, string->characters8(), length);
211        else
212            StringImpl::copyChars(position, string->characters16(), length);
213    }
214
215    ASSERT(buffer == position);
216    ASSERT(!isRope());
217}
218
219void JSRopeString::outOfMemory(ExecState* exec) const
220{
221    for (size_t i = 0; i < s_maxInternalRopeLength && m_fibers[i]; ++i)
222        m_fibers[i].clear();
223    ASSERT(isRope());
224    ASSERT(m_value.isNull());
225    if (exec)
226        throwOutOfMemoryError(exec);
227}
228
229JSString* JSRopeString::getIndexSlowCase(ExecState* exec, unsigned i)
230{
231    ASSERT(isRope());
232    resolveRope(exec);
233    // Return a safe no-value result, this should never be used, since the excetion will be thrown.
234    if (exec->exception())
235        return jsEmptyString(exec);
236    ASSERT(!isRope());
237    RELEASE_ASSERT(i < m_value.length());
238    return jsSingleCharacterSubstring(exec, m_value, i);
239}
240
241JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
242{
243    return const_cast<JSString*>(this);
244}
245
246bool JSString::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
247{
248    result = this;
249    number = jsToNumber(value(exec));
250    return false;
251}
252
253bool JSString::toBoolean() const
254{
255    return m_length;
256}
257
258double JSString::toNumber(ExecState* exec) const
259{
260    return jsToNumber(value(exec));
261}
262
263inline StringObject* StringObject::create(ExecState* exec, JSGlobalObject* globalObject, JSString* string)
264{
265    StringObject* object = new (NotNull, allocateCell<StringObject>(*exec->heap())) StringObject(exec->vm(), globalObject->stringObjectStructure());
266    object->finishCreation(exec->vm(), string);
267    return object;
268}
269
270JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const
271{
272    return StringObject::create(exec, globalObject, const_cast<JSString*>(this));
273}
274
275JSObject* JSString::toThisObject(JSCell* cell, ExecState* exec)
276{
277    return StringObject::create(exec, exec->lexicalGlobalObject(), jsCast<JSString*>(cell));
278}
279
280bool JSString::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
281{
282    JSString* thisObject = jsCast<JSString*>(cell);
283    // The semantics here are really getPropertySlot, not getOwnPropertySlot.
284    // This function should only be called by JSValue::get.
285    if (thisObject->getStringPropertySlot(exec, propertyName, slot))
286        return true;
287    slot.setBase(thisObject);
288    JSObject* object;
289    for (JSValue prototype = exec->lexicalGlobalObject()->stringPrototype(); !prototype.isNull(); prototype = object->prototype()) {
290        object = asObject(prototype);
291        if (object->methodTable()->getOwnPropertySlot(object, exec, propertyName, slot))
292            return true;
293    }
294    slot.setUndefined();
295    return true;
296}
297
298bool JSString::getStringPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
299{
300    if (propertyName == exec->propertyNames().length) {
301        descriptor.setDescriptor(jsNumber(m_length), DontEnum | DontDelete | ReadOnly);
302        return true;
303    }
304
305    unsigned i = propertyName.asIndex();
306    if (i < m_length) {
307        ASSERT(i != PropertyName::NotAnIndex); // No need for an explicit check, the above test would always fail!
308        descriptor.setDescriptor(getIndex(exec, i), DontDelete | ReadOnly);
309        return true;
310    }
311
312    return false;
313}
314
315bool JSString::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, PropertySlot& slot)
316{
317    JSString* thisObject = jsCast<JSString*>(cell);
318    // The semantics here are really getPropertySlot, not getOwnPropertySlot.
319    // This function should only be called by JSValue::get.
320    if (thisObject->getStringPropertySlot(exec, propertyName, slot))
321        return true;
322    return JSString::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, propertyName), slot);
323}
324
325} // namespace JSC
326