1  /*
  2   *  Copyright (C) 1999-2002 Harri Porten (porten@kde.org)
  3   *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
  4   *  Copyright (C) 2004-2019 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 "JSGlobalObjectFunctions.h"
 27  #include "JSGlobalObjectInlines.h"
 28  #include "JSObjectInlines.h"
 29  #include "StringObject.h"
 30  #include "StrongInlines.h"
 31  #include "StructureInlines.h"
 32  
 33  namespace JSC {
 34      
 35  const ClassInfo JSString::s_info = { "string", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSString) };
 36  
 37  Structure* JSString::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue proto)
 38  {
 39      return Structure::create(vm, globalObject, proto, TypeInfo(StringType, StructureFlags), info());
 40  }
 41  
 42  JSString* JSString::createEmptyString(VM& vm)
 43  {
 44      JSString* newString = new (NotNull, allocateCell<JSString>(vm.heap)) JSString(vm, *StringImpl::empty());
 45      newString->finishCreation(vm);
 46      return newString;
 47  }
 48  
 49  template<>
 50  void JSRopeString::RopeBuilder<RecordOverflow>::expand()
 51  {
 52      RELEASE_ASSERT(!this->hasOverflowed());
 53      ASSERT(m_strings.size() == JSRopeString::s_maxInternalRopeLength);
 54      static_assert(3 == JSRopeString::s_maxInternalRopeLength, "");
 55      ASSERT(m_length);
 56      ASSERT(asString(m_strings.at(0))->length());
 57      ASSERT(asString(m_strings.at(1))->length());
 58      ASSERT(asString(m_strings.at(2))->length());
 59  
 60      JSString* string = JSRopeString::create(m_vm, asString(m_strings.at(0)), asString(m_strings.at(1)), asString(m_strings.at(2)));
 61      ASSERT(string->length() == m_length);
 62      m_strings.clear();
 63      m_strings.append(string);
 64  }
 65  
 66  void JSString::dumpToStream(const JSCell* cell, PrintStream& out)
 67  {
 68      VM& vm = cell->vm();
 69      const JSString* thisObject = jsCast<const JSString*>(cell);
 70      out.printf("<%p, %s, [%u], ", thisObject, thisObject->className(vm), thisObject->length());
 71      uintptr_t pointer = thisObject->m_fiber;
 72      if (pointer & isRopeInPointer) {
 73          if (pointer & JSRopeString::isSubstringInPointer)
 74              out.printf("[substring]");
 75          else
 76              out.printf("[rope]");
 77      } else {
 78          if (WTF::StringImpl* ourImpl = bitwise_cast<StringImpl*>(pointer)) {
 79              if (ourImpl->is8Bit())
 80                  out.printf("[8 %p]", ourImpl->characters8());
 81              else
 82                  out.printf("[16 %p]", ourImpl->characters16());
 83          }
 84      }
 85      out.printf(">");
 86  }
 87  
 88  bool JSString::equalSlowCase(JSGlobalObject* globalObject, JSString* other) const
 89  {
 90      VM& vm = globalObject->vm();
 91      auto scope = DECLARE_THROW_SCOPE(vm);
 92      String str1 = value(globalObject);
 93      RETURN_IF_EXCEPTION(scope, false);
 94      String str2 = other->value(globalObject);
 95      RETURN_IF_EXCEPTION(scope, false);
 96      return WTF::equal(*str1.impl(), *str2.impl());
 97  }
 98  
 99  size_t JSString::estimatedSize(JSCell* cell, VM& vm)
100  {
101      JSString* thisObject = asString(cell);
102      uintptr_t pointer = thisObject->m_fiber;
103      if (pointer & isRopeInPointer)
104          return Base::estimatedSize(cell, vm);
105      return Base::estimatedSize(cell, vm) + bitwise_cast<StringImpl*>(pointer)->costDuringGC();
106  }
107  
108  void JSString::visitChildren(JSCell* cell, SlotVisitor& visitor)
109  {
110      JSString* thisObject = asString(cell);
111      ASSERT_GC_OBJECT_INHERITS(thisObject, info());
112      Base::visitChildren(thisObject, visitor);
113      
114      uintptr_t pointer = thisObject->m_fiber;
115      if (pointer & isRopeInPointer) {
116          if (pointer & JSRopeString::isSubstringInPointer) {
117              visitor.appendUnbarriered(static_cast<JSRopeString*>(thisObject)->fiber1());
118              return;
119          }
120          for (unsigned index = 0; index < JSRopeString::s_maxInternalRopeLength; ++index) {
121              JSString* fiber = nullptr;
122              switch (index) {
123              case 0:
124                  fiber = bitwise_cast<JSString*>(pointer & JSRopeString::stringMask);
125                  break;
126              case 1:
127                  fiber = static_cast<JSRopeString*>(thisObject)->fiber1();
128                  break;
129              case 2:
130                  fiber = static_cast<JSRopeString*>(thisObject)->fiber2();
131                  break;
132              default:
133                  ASSERT_NOT_REACHED();
134                  return;
135              }
136              if (!fiber)
137                  break;
138              visitor.appendUnbarriered(fiber);
139          }
140          return;
141      }
142      if (StringImpl* impl = bitwise_cast<StringImpl*>(pointer))
143          visitor.reportExtraMemoryVisited(impl->costDuringGC());
144  }
145  
146  static constexpr unsigned maxLengthForOnStackResolve = 2048;
147  
148  void JSRopeString::resolveRopeInternal8(LChar* buffer) const
149  {
150      if (isSubstring()) {
151          StringImpl::copyCharacters(buffer, substringBase()->valueInternal().characters8() + substringOffset(), length());
152          return;
153      }
154      
155      resolveRopeInternalNoSubstring(buffer);
156  }
157  
158  void JSRopeString::resolveRopeInternal16(UChar* buffer) const
159  {
160      if (isSubstring()) {
161          StringImpl::copyCharacters(
162              buffer, substringBase()->valueInternal().characters16() + substringOffset(), length());
163          return;
164      }
165      
166      resolveRopeInternalNoSubstring(buffer);
167  }
168  
169  template<typename CharacterType>
170  void JSRopeString::resolveRopeInternalNoSubstring(CharacterType* buffer) const
171  {
172      for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
173          if (fiber(i)->isRope()) {
174              resolveRopeSlowCase(buffer);
175              return;
176          }
177      }
178  
179      CharacterType* position = buffer;
180      for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i) {
181          const StringImpl& fiberString = *fiber(i)->valueInternal().impl();
182          unsigned length = fiberString.length();
183          if (fiberString.is8Bit())
184              StringImpl::copyCharacters(position, fiberString.characters8(), length);
185          else
186              StringImpl::copyCharacters(position, fiberString.characters16(), length);
187          position += length;
188      }
189      ASSERT((buffer + length()) == position);
190  }
191  
192  AtomString JSRopeString::resolveRopeToAtomString(JSGlobalObject* globalObject) const
193  {
194      VM& vm = globalObject->vm();
195      auto scope = DECLARE_THROW_SCOPE(vm);
196  
197      if (length() > maxLengthForOnStackResolve) {
198          scope.release();
199          return resolveRopeWithFunction(globalObject, [&] (Ref<StringImpl>&& newImpl) {
200              return AtomStringImpl::add(newImpl.ptr());
201          });
202      }
203  
204      if (is8Bit()) {
205          LChar buffer[maxLengthForOnStackResolve];
206          resolveRopeInternal8(buffer);
207          convertToNonRope(AtomStringImpl::add(buffer, length()));
208      } else {
209          UChar buffer[maxLengthForOnStackResolve];
210          resolveRopeInternal16(buffer);
211          convertToNonRope(AtomStringImpl::add(buffer, length()));
212      }
213  
214      // If we resolved a string that didn't previously exist, notify the heap that we've grown.
215      if (valueInternal().impl()->hasOneRef())
216          vm.heap.reportExtraMemoryAllocated(valueInternal().impl()->cost());
217      return valueInternal();
218  }
219  
220  inline void JSRopeString::convertToNonRope(String&& string) const
221  {
222      // Concurrent compiler threads can access String held by JSString. So we always emit
223      // store-store barrier here to ensure concurrent compiler threads see initialized String.
224      ASSERT(JSString::isRope());
225      WTF::storeStoreFence();
226      new (&uninitializedValueInternal()) String(WTFMove(string));
227      static_assert(sizeof(String) == sizeof(RefPtr<StringImpl>), "JSString's String initialization must be done in one pointer move.");
228      // We do not clear the trailing fibers and length information (fiber1 and fiber2) because we could be reading the length concurrently.
229      ASSERT(!JSString::isRope());
230  }
231  
232  RefPtr<AtomStringImpl> JSRopeString::resolveRopeToExistingAtomString(JSGlobalObject* globalObject) const
233  {
234      VM& vm = globalObject->vm();
235      auto scope = DECLARE_THROW_SCOPE(vm);
236  
237      if (length() > maxLengthForOnStackResolve) {
238          RefPtr<AtomStringImpl> existingAtomString;
239          resolveRopeWithFunction(globalObject, [&] (Ref<StringImpl>&& newImpl) -> Ref<StringImpl> {
240              existingAtomString = AtomStringImpl::lookUp(newImpl.ptr());
241              if (existingAtomString)
242                  return makeRef(*existingAtomString);
243              return WTFMove(newImpl);
244          });
245          RETURN_IF_EXCEPTION(scope, nullptr);
246          return existingAtomString;
247      }
248      
249      if (is8Bit()) {
250          LChar buffer[maxLengthForOnStackResolve];
251          resolveRopeInternal8(buffer);
252          if (RefPtr<AtomStringImpl> existingAtomString = AtomStringImpl::lookUp(buffer, length())) {
253              convertToNonRope(*existingAtomString);
254              return existingAtomString;
255          }
256      } else {
257          UChar buffer[maxLengthForOnStackResolve];
258          resolveRopeInternal16(buffer);
259          if (RefPtr<AtomStringImpl> existingAtomString = AtomStringImpl::lookUp(buffer, length())) {
260              convertToNonRope(*existingAtomString);
261              return existingAtomString;
262          }
263      }
264  
265      return nullptr;
266  }
267  
268  template<typename Function>
269  const String& JSRopeString::resolveRopeWithFunction(JSGlobalObject* nullOrGlobalObjectForOOM, Function&& function) const
270  {
271      ASSERT(isRope());
272      
273      VM& vm = this->vm();
274      if (isSubstring()) {
275          ASSERT(!substringBase()->isRope());
276          auto newImpl = substringBase()->valueInternal().substringSharingImpl(substringOffset(), length());
277          convertToNonRope(function(newImpl.releaseImpl().releaseNonNull()));
278          return valueInternal();
279      }
280      
281      if (is8Bit()) {
282          LChar* buffer;
283          auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer);
284          if (!newImpl) {
285              outOfMemory(nullOrGlobalObjectForOOM);
286              return nullString();
287          }
288          vm.heap.reportExtraMemoryAllocated(newImpl->cost());
289  
290          resolveRopeInternalNoSubstring(buffer);
291          convertToNonRope(function(newImpl.releaseNonNull()));
292          return valueInternal();
293      }
294      
295      UChar* buffer;
296      auto newImpl = StringImpl::tryCreateUninitialized(length(), buffer);
297      if (!newImpl) {
298          outOfMemory(nullOrGlobalObjectForOOM);
299          return nullString();
300      }
301      vm.heap.reportExtraMemoryAllocated(newImpl->cost());
302      
303      resolveRopeInternalNoSubstring(buffer);
304      convertToNonRope(function(newImpl.releaseNonNull()));
305      return valueInternal();
306  }
307  
308  const String& JSRopeString::resolveRope(JSGlobalObject* nullOrGlobalObjectForOOM) const
309  {
310      return resolveRopeWithFunction(nullOrGlobalObjectForOOM, [] (Ref<StringImpl>&& newImpl) {
311          return WTFMove(newImpl);
312      });
313  }
314  
315  // Overview: These functions convert a JSString from holding a string in rope form
316  // down to a simple String representation. It does so by building up the string
317  // backwards, since we want to avoid recursion, we expect that the tree structure
318  // representing the rope is likely imbalanced with more nodes down the left side
319  // (since appending to the string is likely more common) - and as such resolving
320  // in this fashion should minimize work queue size.  (If we built the queue forwards
321  // we would likely have to place all of the constituent StringImpls into the
322  // Vector before performing any concatenation, but by working backwards we likely
323  // only fill the queue with the number of substrings at any given level in a
324  // rope-of-ropes.)
325  template<typename CharacterType>
326  void JSRopeString::resolveRopeSlowCase(CharacterType* buffer) const
327  {
328      CharacterType* position = buffer + length(); // We will be working backwards over the rope.
329      Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.
330  
331      for (size_t i = 0; i < s_maxInternalRopeLength && fiber(i); ++i)
332          workQueue.append(fiber(i));
333  
334      while (!workQueue.isEmpty()) {
335          JSString* currentFiber = workQueue.last();
336          workQueue.removeLast();
337  
338          if (currentFiber->isRope()) {
339              JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
340              if (currentFiberAsRope->isSubstring()) {
341                  ASSERT(!currentFiberAsRope->substringBase()->isRope());
342                  StringImpl* string = static_cast<StringImpl*>(
343                      currentFiberAsRope->substringBase()->valueInternal().impl());
344                  unsigned offset = currentFiberAsRope->substringOffset();
345                  unsigned length = currentFiberAsRope->length();
346                  position -= length;
347                  if (string->is8Bit())
348                      StringImpl::copyCharacters(position, string->characters8() + offset, length);
349                  else
350                      StringImpl::copyCharacters(position, string->characters16() + offset, length);
351                  continue;
352              }
353              for (size_t i = 0; i < s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
354                  workQueue.append(currentFiberAsRope->fiber(i));
355              continue;
356          }
357  
358          StringImpl* string = static_cast<StringImpl*>(currentFiber->valueInternal().impl());
359          unsigned length = string->length();
360          position -= length;
361          if (string->is8Bit())
362              StringImpl::copyCharacters(position, string->characters8(), length);
363          else
364              StringImpl::copyCharacters(position, string->characters16(), length);
365      }
366  
367      ASSERT(buffer == position);
368  }
369  
370  void JSRopeString::outOfMemory(JSGlobalObject* nullOrGlobalObjectForOOM) const
371  {
372      ASSERT(isRope());
373      if (nullOrGlobalObjectForOOM) {
374          VM& vm = nullOrGlobalObjectForOOM->vm();
375          auto scope = DECLARE_THROW_SCOPE(vm);
376          throwOutOfMemoryError(nullOrGlobalObjectForOOM, scope);
377      }
378  }
379  
380  JSValue JSString::toPrimitive(JSGlobalObject*, PreferredPrimitiveType) const
381  {
382      return const_cast<JSString*>(this);
383  }
384  
385  double JSString::toNumber(JSGlobalObject* globalObject) const
386  {
387      VM& vm = globalObject->vm();
388      auto scope = DECLARE_THROW_SCOPE(vm);
389      StringView view = unsafeView(globalObject);
390      RETURN_IF_EXCEPTION(scope, 0);
391      return jsToNumber(view);
392  }
393  
394  inline StringObject* StringObject::create(VM& vm, JSGlobalObject* globalObject, JSString* string)
395  {
396      StringObject* object = new (NotNull, allocateCell<StringObject>(vm.heap)) StringObject(vm, globalObject->stringObjectStructure());
397      object->finishCreation(vm, string);
398      return object;
399  }
400  
401  JSObject* JSString::toObject(JSGlobalObject* globalObject) const
402  {
403      return StringObject::create(globalObject->vm(), globalObject, const_cast<JSString*>(this));
404  }
405  
406  JSValue JSString::toThis(JSCell* cell, JSGlobalObject* globalObject, ECMAMode ecmaMode)
407  {
408      if (ecmaMode.isStrict())
409          return cell;
410      return StringObject::create(globalObject->vm(), globalObject, asString(cell));
411  }
412  
413  bool JSString::getStringPropertyDescriptor(JSGlobalObject* globalObject, PropertyName propertyName, PropertyDescriptor& descriptor)
414  {
415      VM& vm = globalObject->vm();
416      if (propertyName == vm.propertyNames->length) {
417          descriptor.setDescriptor(jsNumber(length()), PropertyAttribute::DontEnum | PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
418          return true;
419      }
420      
421      Optional<uint32_t> index = parseIndex(propertyName);
422      if (index && index.value() < length()) {
423          descriptor.setDescriptor(getIndex(globalObject, index.value()), PropertyAttribute::DontDelete | PropertyAttribute::ReadOnly);
424          return true;
425      }
426      
427      return false;
428  }
429  
430  JSString* jsStringWithCacheSlowCase(VM& vm, StringImpl& stringImpl)
431  {
432      if (JSString* string = vm.stringCache.get(&stringImpl))
433          return string;
434  
435      JSString* string = jsString(vm, String(stringImpl));
436      vm.lastCachedString.set(vm, string);
437      return string;
438  }
439  
440  } // namespace JSC