2011-01-27 Oliver Hunt <oliver@apple.com>
[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 "Operations.h"
30 #include "StringObject.h"
31 #include "StringPrototype.h"
32
33 namespace JSC {
34     
35 static const unsigned substringFromRopeCutoff = 4;
36
37 // Overview: this methods converts a JSString from holding a string in rope form
38 // down to a simple UString representation.  It does so by building up the string
39 // backwards, since we want to avoid recursion, we expect that the tree structure
40 // representing the rope is likely imbalanced with more nodes down the left side
41 // (since appending to the string is likely more common) - and as such resolving
42 // in this fashion should minimize work queue size.  (If we built the queue forwards
43 // we would likely have to place all of the constituent StringImpls into the
44 // Vector before performing any concatenation, but by working backwards we likely
45 // only fill the queue with the number of substrings at any given level in a
46 // rope-of-ropes.)
47 void JSString::resolveRope(ExecState* exec) const
48 {
49     ASSERT(isRope());
50
51     // Allocate the buffer to hold the final string, position initially points to the end.
52     UChar* buffer;
53     if (PassRefPtr<StringImpl> newImpl = StringImpl::tryCreateUninitialized(m_length, buffer))
54         m_value = newImpl;
55     else {
56         for (unsigned i = 0; i < m_fiberCount; ++i) {
57             RopeImpl::deref(m_other.m_fibers[i]);
58             m_other.m_fibers[i] = 0;
59         }
60         m_fiberCount = 0;
61         ASSERT(!isRope());
62         ASSERT(m_value == UString());
63         if (exec)
64             throwOutOfMemoryError(exec);
65         return;
66     }
67     UChar* position = buffer + m_length;
68
69     // Start with the current RopeImpl.
70     Vector<RopeImpl::Fiber, 32> workQueue;
71     RopeImpl::Fiber currentFiber;
72     for (unsigned i = 0; i < (m_fiberCount - 1); ++i)
73         workQueue.append(m_other.m_fibers[i]);
74     currentFiber = m_other.m_fibers[m_fiberCount - 1];
75     while (true) {
76         if (RopeImpl::isRope(currentFiber)) {
77             RopeImpl* rope = static_cast<RopeImpl*>(currentFiber);
78             // Copy the contents of the current rope into the workQueue, with the last item in 'currentFiber'
79             // (we will be working backwards over the rope).
80             unsigned fiberCountMinusOne = rope->fiberCount() - 1;
81             for (unsigned i = 0; i < fiberCountMinusOne; ++i)
82                 workQueue.append(rope->fibers()[i]);
83             currentFiber = rope->fibers()[fiberCountMinusOne];
84         } else {
85             StringImpl* string = static_cast<StringImpl*>(currentFiber);
86             unsigned length = string->length();
87             position -= length;
88             StringImpl::copyChars(position, string->characters(), length);
89
90             // Was this the last item in the work queue?
91             if (workQueue.isEmpty()) {
92                 // Create a string from the UChar buffer, clear the rope RefPtr.
93                 ASSERT(buffer == position);
94                 for (unsigned i = 0; i < m_fiberCount; ++i) {
95                     RopeImpl::deref(m_other.m_fibers[i]);
96                     m_other.m_fibers[i] = 0;
97                 }
98                 m_fiberCount = 0;
99
100                 ASSERT(!isRope());
101                 return;
102             }
103
104             // No! - set the next item up to process.
105             currentFiber = workQueue.last();
106             workQueue.removeLast();
107         }
108     }
109 }
110     
111 // This function construsts a substring out of a rope without flattening by reusing the existing fibers.
112 // This can reduce memory usage substantially. Since traversing ropes is slow the function will revert 
113 // back to flattening if the rope turns out to be long.
114 JSString* JSString::substringFromRope(ExecState* exec, unsigned substringStart, unsigned substringLength)
115 {
116     ASSERT(isRope());
117     ASSERT(substringLength);
118     
119     JSGlobalData* globalData = &exec->globalData();
120
121     UString substringFibers[3];
122     
123     unsigned fiberCount = 0;
124     unsigned substringFiberCount = 0;
125     unsigned substringEnd = substringStart + substringLength;
126     unsigned fiberEnd = 0;
127
128     RopeIterator end;
129     for (RopeIterator it(m_other.m_fibers.data(), m_fiberCount); it != end; ++it) {
130         ++fiberCount;
131         StringImpl* fiberString = *it;
132         unsigned fiberStart = fiberEnd;
133         fiberEnd = fiberStart + fiberString->length();
134         if (fiberEnd <= substringStart)
135             continue;
136         unsigned copyStart = std::max(substringStart, fiberStart);
137         unsigned copyEnd = std::min(substringEnd, fiberEnd);
138         if (copyStart == fiberStart && copyEnd == fiberEnd)
139             substringFibers[substringFiberCount++] = UString(fiberString);
140         else
141             substringFibers[substringFiberCount++] = UString(StringImpl::create(fiberString, copyStart - fiberStart, copyEnd - copyStart));
142         if (fiberEnd >= substringEnd)
143             break;
144         if (fiberCount > substringFromRopeCutoff || substringFiberCount >= 3) {
145             // This turned out to be a really inefficient rope. Just flatten it.
146             resolveRope(exec);
147             return jsSubstring(&exec->globalData(), m_value, substringStart, substringLength);
148         }
149     }
150     ASSERT(substringFiberCount && substringFiberCount <= 3);
151
152     if (substringLength == 1) {
153         ASSERT(substringFiberCount == 1);
154         UChar c = substringFibers[0].characters()[0];
155         if (c <= 0xFF)
156             return globalData->smallStrings.singleCharacterString(globalData, c);
157     }
158     if (substringFiberCount == 1)
159         return new (globalData) JSString(globalData, substringFibers[0]);
160     if (substringFiberCount == 2)
161         return new (globalData) JSString(globalData, substringFibers[0], substringFibers[1]);
162     return new (globalData) JSString(globalData, substringFibers[0], substringFibers[1], substringFibers[2]);
163 }
164
165 JSValue JSString::replaceCharacter(ExecState* exec, UChar character, const UString& replacement)
166 {
167     if (!isRope()) {
168         size_t matchPosition = m_value.find(character);
169         if (matchPosition == notFound)
170             return JSValue(this);
171         return jsString(exec, m_value.substringSharingImpl(0, matchPosition), replacement, m_value.substringSharingImpl(matchPosition + 1));
172     }
173
174     RopeIterator end;
175     
176     // Count total fibers and find matching string.
177     size_t fiberCount = 0;
178     StringImpl* matchString = 0;
179     size_t matchPosition = notFound;
180     for (RopeIterator it(m_other.m_fibers.data(), m_fiberCount); it != end; ++it) {
181         ++fiberCount;
182         if (matchString)
183             continue;
184
185         StringImpl* string = *it;
186         matchPosition = string->find(character);
187         if (matchPosition == notFound)
188             continue;
189         matchString = string;
190     }
191
192     if (!matchString)
193         return this;
194
195     RopeBuilder builder(replacement.length() ? fiberCount + 2 : fiberCount + 1);
196     if (UNLIKELY(builder.isOutOfMemory()))
197         return throwOutOfMemoryError(exec);
198
199     for (RopeIterator it(m_other.m_fibers.data(), m_fiberCount); it != end; ++it) {
200         StringImpl* string = *it;
201         if (string != matchString) {
202             builder.append(UString(string));
203             continue;
204         }
205
206         builder.append(UString(string).substringSharingImpl(0, matchPosition));
207         if (replacement.length())
208             builder.append(replacement);
209         builder.append(UString(string).substringSharingImpl(matchPosition + 1));
210         matchString = 0;
211     }
212
213     JSGlobalData* globalData = &exec->globalData();
214     return JSValue(new (globalData) JSString(globalData, builder.release()));
215 }
216
217 JSString* JSString::getIndexSlowCase(ExecState* exec, unsigned i)
218 {
219     ASSERT(isRope());
220     resolveRope(exec);
221     // Return a safe no-value result, this should never be used, since the excetion will be thrown.
222     if (exec->exception())
223         return jsString(exec, "");
224     ASSERT(!isRope());
225     ASSERT(i < m_value.length());
226     return jsSingleCharacterSubstring(exec, m_value, i);
227 }
228
229 JSValue JSString::toPrimitive(ExecState*, PreferredPrimitiveType) const
230 {
231     return const_cast<JSString*>(this);
232 }
233
234 bool JSString::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result)
235 {
236     result = this;
237     number = jsToNumber(value(exec));
238     return false;
239 }
240
241 bool JSString::toBoolean(ExecState*) const
242 {
243     return m_length;
244 }
245
246 double JSString::toNumber(ExecState* exec) const
247 {
248     return jsToNumber(value(exec));
249 }
250
251 UString JSString::toString(ExecState* exec) const
252 {
253     return value(exec);
254 }
255
256 inline StringObject* StringObject::create(ExecState* exec, JSString* string)
257 {
258     return new (exec) StringObject(exec->globalData(), exec->lexicalGlobalObject()->stringObjectStructure(), string);
259 }
260
261 JSObject* JSString::toObject(ExecState* exec) const
262 {
263     return StringObject::create(exec, const_cast<JSString*>(this));
264 }
265
266 JSObject* JSString::toThisObject(ExecState* exec) const
267 {
268     return StringObject::create(exec, const_cast<JSString*>(this));
269 }
270
271 bool JSString::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
272 {
273     // The semantics here are really getPropertySlot, not getOwnPropertySlot.
274     // This function should only be called by JSValue::get.
275     if (getStringPropertySlot(exec, propertyName, slot))
276         return true;
277     if (propertyName == exec->propertyNames().underscoreProto) {
278         slot.setValue(exec->lexicalGlobalObject()->stringPrototype());
279         return true;
280     }
281     slot.setBase(this);
282     JSObject* object;
283     for (JSValue prototype = exec->lexicalGlobalObject()->stringPrototype(); !prototype.isNull(); prototype = object->prototype()) {
284         object = asObject(prototype);
285         if (object->getOwnPropertySlot(exec, propertyName, slot))
286             return true;
287     }
288     slot.setUndefined();
289     return true;
290 }
291
292 bool JSString::getStringPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
293 {
294     if (propertyName == exec->propertyNames().length) {
295         descriptor.setDescriptor(jsNumber(m_length), DontEnum | DontDelete | ReadOnly);
296         return true;
297     }
298     
299     bool isStrictUInt32;
300     unsigned i = propertyName.toUInt32(isStrictUInt32);
301     if (isStrictUInt32 && i < m_length) {
302         descriptor.setDescriptor(getIndex(exec, i), DontDelete | ReadOnly);
303         return true;
304     }
305     
306     return false;
307 }
308
309 bool JSString::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
310 {
311     if (getStringPropertyDescriptor(exec, propertyName, descriptor))
312         return true;
313     if (propertyName != exec->propertyNames().underscoreProto)
314         return false;
315     descriptor.setDescriptor(exec->lexicalGlobalObject()->stringPrototype(), DontEnum);
316     return true;
317 }
318
319 bool JSString::getOwnPropertySlot(ExecState* exec, unsigned propertyName, PropertySlot& slot)
320 {
321     // The semantics here are really getPropertySlot, not getOwnPropertySlot.
322     // This function should only be called by JSValue::get.
323     if (getStringPropertySlot(exec, propertyName, slot))
324         return true;
325     return JSString::getOwnPropertySlot(exec, Identifier::from(exec, propertyName), slot);
326 }
327
328 } // namespace JSC