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