1 /* 2 * Copyright (C) 1999-2002 Harri Porten (porten (at) kde.org) 3 * Copyright (C) 2001 Peter Kelly (pmk (at) 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 <= maxSingleCharacterString) 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, JSGlobalObject* globalObject, JSString* string) 257 { 258 return new (exec) StringObject(exec->globalData(), globalObject->stringObjectStructure(), string); 259 } 260 261 JSObject* JSString::toObject(ExecState* exec, JSGlobalObject* globalObject) const 262 { 263 return StringObject::create(exec, globalObject, const_cast<JSString*>(this)); 264 } 265 266 JSObject* JSString::toThisObject(ExecState* exec) const 267 { 268 return StringObject::create(exec, exec->lexicalGlobalObject(), 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 329