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