1  /*
  2   * Copyright (C) 2009-2020 Apple Inc. All rights reserved.
  3   * Copyright (C) 2020 Alexey Shvayka <shvaikalesh@gmail.com>.
  4   *
  5   * Redistribution and use in source and binary forms, with or without
  6   * modification, are permitted provided that the following conditions
  7   * are met:
  8   * 1. Redistributions of source code must retain the above copyright
  9   *    notice, this list of conditions and the following disclaimer.
 10   * 2. Redistributions in binary form must reproduce the above copyright
 11   *    notice, this list of conditions and the following disclaimer in the
 12   *    documentation and/or other materials provided with the distribution.
 13   *
 14   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 15   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 16   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 17   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 18   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 19   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 20   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 21   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 22   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 23   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 24   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 25   */
 26  
 27  #include "config.h"
 28  #include "JSONObject.h"
 29  
 30  #include "ArrayConstructor.h"
 31  #include "BigIntObject.h"
 32  #include "BooleanObject.h"
 33  #include "JSArrayInlines.h"
 34  #include "JSCInlines.h"
 35  #include "LiteralParser.h"
 36  #include "ObjectConstructor.h"
 37  #include "PropertyNameArray.h"
 38  #include "VMInlines.h"
 39  #include <wtf/text/StringBuilder.h>
 40  
 41  namespace JSC {
 42  
 43  STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSONObject);
 44  
 45  static JSC_DECLARE_HOST_FUNCTION(JSONProtoFuncParse);
 46  static JSC_DECLARE_HOST_FUNCTION(JSONProtoFuncStringify);
 47  
 48  }
 49  
 50  #include "JSONObject.lut.h"
 51  
 52  namespace JSC {
 53  
 54  JSONObject::JSONObject(VM& vm, Structure* structure)
 55      : JSNonFinalObject(vm, structure)
 56  {
 57  }
 58  
 59  void JSONObject::finishCreation(VM& vm)
 60  {
 61      Base::finishCreation(vm);
 62      ASSERT(inherits(vm, info()));
 63      JSC_TO_STRING_TAG_WITHOUT_TRANSITION();
 64  }
 65  
 66  // PropertyNameForFunctionCall objects must be on the stack, since the JSValue that they create is not marked.
 67  class PropertyNameForFunctionCall {
 68  public:
 69      PropertyNameForFunctionCall(const Identifier&);
 70      PropertyNameForFunctionCall(unsigned);
 71  
 72      JSValue value(JSGlobalObject*) const;
 73  
 74  private:
 75      const Identifier* m_identifier;
 76      unsigned m_number;
 77      mutable JSValue m_value;
 78  };
 79  
 80  class Stringifier {
 81      WTF_MAKE_NONCOPYABLE(Stringifier);
 82      WTF_FORBID_HEAP_ALLOCATION;
 83  public:
 84      Stringifier(JSGlobalObject*, JSValue replacer, JSValue space);
 85      JSValue stringify(JSValue);
 86  
 87  private:
 88      class Holder {
 89      public:
 90          enum RootHolderTag { RootHolder };
 91          Holder(JSGlobalObject*, JSObject*);
 92          Holder(RootHolderTag, JSObject*);
 93  
 94          JSObject* object() const { return m_object; }
 95          bool isArray() const { return m_isArray; }
 96  
 97          bool appendNextProperty(Stringifier&, StringBuilder&);
 98  
 99      private:
100          JSObject* m_object;
101          const bool m_isJSArray;
102          const bool m_isArray;
103          unsigned m_index { 0 };
104          unsigned m_size { 0 };
105          RefPtr<PropertyNameArrayData> m_propertyNames;
106      };
107  
108      friend class Holder;
109  
110      JSValue toJSON(JSValue, const PropertyNameForFunctionCall&);
111  
112      enum StringifyResult { StringifyFailed, StringifySucceeded, StringifyFailedDueToUndefinedOrSymbolValue };
113      StringifyResult appendStringifiedValue(StringBuilder&, JSValue, const Holder&, const PropertyNameForFunctionCall&);
114  
115      bool willIndent() const;
116      void indent();
117      void unindent();
118      void startNewLine(StringBuilder&) const;
119      bool isCallableReplacer() const { return m_replacerCallData.type != CallData::Type::None; }
120  
121      JSGlobalObject* const m_globalObject;
122      JSValue m_replacer;
123      bool m_usingArrayReplacer { false };
124      PropertyNameArray m_arrayReplacerPropertyNames;
125      CallData m_replacerCallData;
126      String m_gap;
127  
128      MarkedArgumentBuffer m_objectStack;
129      Vector<Holder, 16, UnsafeVectorOverflow> m_holderStack;
130      String m_repeatedGap;
131      String m_indent;
132  };
133  
134  // ------------------------------ helper functions --------------------------------
135  
136  static inline JSValue unwrapBoxedPrimitive(JSGlobalObject* globalObject, JSValue value)
137  {
138      VM& vm = globalObject->vm();
139      if (!value.isObject())
140          return value;
141      JSObject* object = asObject(value);
142      if (object->inherits<NumberObject>(vm))
143          return jsNumber(object->toNumber(globalObject));
144      if (object->inherits<StringObject>(vm))
145          return object->toString(globalObject);
146      if (object->inherits<BooleanObject>(vm) || object->inherits<BigIntObject>(vm))
147          return jsCast<JSWrapperObject*>(object)->internalValue();
148  
149      // Do not unwrap SymbolObject to Symbol. It is not performed in the spec.
150      // http://www.ecma-international.org/ecma-262/6.0/#sec-serializejsonproperty
151      return value;
152  }
153  
154  static inline String gap(JSGlobalObject* globalObject, JSValue space)
155  {
156      VM& vm = globalObject->vm();
157      auto scope = DECLARE_THROW_SCOPE(vm);
158  
159      const unsigned maxGapLength = 10;
160      space = unwrapBoxedPrimitive(globalObject, space);
161      RETURN_IF_EXCEPTION(scope, { });
162  
163      // If the space value is a number, create a gap string with that number of spaces.
164      if (space.isNumber()) {
165          double spaceCount = space.asNumber();
166          int count;
167          if (spaceCount > maxGapLength)
168              count = maxGapLength;
169          else if (!(spaceCount > 0))
170              count = 0;
171          else
172              count = static_cast<int>(spaceCount);
173          char spaces[maxGapLength];
174          for (int i = 0; i < count; ++i)
175              spaces[i] = ' ';
176          return String(spaces, count);
177      }
178  
179      // If the space value is a string, use it as the gap string, otherwise use no gap string.
180      String spaces = space.getString(globalObject);
181      RETURN_IF_EXCEPTION(scope, { });
182      if (spaces.length() <= maxGapLength)
183          return spaces;
184      return spaces.substringSharingImpl(0, maxGapLength);
185  }
186  
187  // ------------------------------ PropertyNameForFunctionCall --------------------------------
188  
189  inline PropertyNameForFunctionCall::PropertyNameForFunctionCall(const Identifier& identifier)
190      : m_identifier(&identifier)
191  {
192  }
193  
194  inline PropertyNameForFunctionCall::PropertyNameForFunctionCall(unsigned number)
195      : m_identifier(nullptr)
196      , m_number(number)
197  {
198  }
199  
200  JSValue PropertyNameForFunctionCall::value(JSGlobalObject* globalObject) const
201  {
202      if (!m_value) {
203          VM& vm = globalObject->vm();
204          if (m_identifier)
205              m_value = jsString(vm, m_identifier->string());
206          else {
207              if (m_number <= 9)
208                  return vm.smallStrings.singleCharacterString(m_number + '0');
209              m_value = jsNontrivialString(vm, vm.numericStrings.add(m_number));
210          }
211      }
212      return m_value;
213  }
214  
215  // ------------------------------ Stringifier --------------------------------
216  
217  Stringifier::Stringifier(JSGlobalObject* globalObject, JSValue replacer, JSValue space)
218      : m_globalObject(globalObject)
219      , m_replacer(replacer)
220      , m_arrayReplacerPropertyNames(globalObject->vm(), PropertyNameMode::Strings, PrivateSymbolMode::Exclude)
221  {
222      VM& vm = globalObject->vm();
223      auto scope = DECLARE_THROW_SCOPE(vm);
224  
225      if (m_replacer.isObject()) {
226          JSObject* replacerObject = asObject(m_replacer);
227  
228          m_replacerCallData = getCallData(vm, replacerObject);
229          if (m_replacerCallData.type == CallData::Type::None) {
230              bool isArrayReplacer = JSC::isArray(globalObject, replacerObject);
231              RETURN_IF_EXCEPTION(scope, );
232              if (isArrayReplacer) {
233                  m_usingArrayReplacer = true;
234                  uint64_t length = static_cast<uint64_t>(toLength(globalObject, replacerObject));
235                  RETURN_IF_EXCEPTION(scope, );
236                  for (uint64_t index = 0; index < length; ++index) {
237                      JSValue name;
238                      if (isJSArray(replacerObject) && replacerObject->canGetIndexQuickly(index))
239                          name = replacerObject->getIndexQuickly(static_cast<uint32_t>(index));
240                      else {
241                          name = replacerObject->get(globalObject, index);
242                          RETURN_IF_EXCEPTION(scope, );
243                      }
244                      if (name.isObject()) {
245                          auto* nameObject = jsCast<JSObject*>(name);
246                          if (!nameObject->inherits<NumberObject>(vm) && !nameObject->inherits<StringObject>(vm))
247                              continue;
248                      } else if (!name.isNumber() && !name.isString())
249                          continue;
250                      JSString* propertyNameString = name.toString(globalObject);
251                      RETURN_IF_EXCEPTION(scope, );
252                      auto propertyName = propertyNameString->toIdentifier(globalObject);
253                      RETURN_IF_EXCEPTION(scope, );
254                      m_arrayReplacerPropertyNames.add(WTFMove(propertyName));
255                  }
256              }
257          }
258      }
259  
260      scope.release();
261      m_gap = gap(globalObject, space);
262  }
263  
264  JSValue Stringifier::stringify(JSValue value)
265  {
266      VM& vm = m_globalObject->vm();
267      auto scope = DECLARE_THROW_SCOPE(vm);
268  
269      PropertyNameForFunctionCall emptyPropertyName(vm.propertyNames->emptyIdentifier);
270  
271      // If the replacer is not callable, root object wrapper is non-user-observable.
272      // We can skip creating this wrapper object.
273      JSObject* object = nullptr;
274      if (isCallableReplacer()) {
275          object = constructEmptyObject(m_globalObject);
276          object->putDirect(vm, vm.propertyNames->emptyIdentifier, value);
277      }
278  
279      StringBuilder result(StringBuilder::OverflowHandler::RecordOverflow);
280      Holder root(Holder::RootHolder, object);
281      auto stringifyResult = appendStringifiedValue(result, value, root, emptyPropertyName);
282      RETURN_IF_EXCEPTION(scope, jsUndefined());
283      if (UNLIKELY(result.hasOverflowed())) {
284          throwOutOfMemoryError(m_globalObject, scope);
285          return jsUndefined();
286      }
287      if (UNLIKELY(stringifyResult != StringifySucceeded))
288          return jsUndefined();
289      RELEASE_AND_RETURN(scope, jsString(vm, result.toString()));
290  }
291  
292  ALWAYS_INLINE JSValue Stringifier::toJSON(JSValue baseValue, const PropertyNameForFunctionCall& propertyName)
293  {
294      VM& vm = m_globalObject->vm();
295      auto scope = DECLARE_THROW_SCOPE(vm);
296      scope.assertNoException();
297  
298      JSValue toJSONFunction = baseValue.get(m_globalObject, vm.propertyNames->toJSON);
299      RETURN_IF_EXCEPTION(scope, { });
300  
301      auto callData = getCallData(vm, toJSONFunction);
302      if (callData.type == CallData::Type::None)
303          return baseValue;
304  
305      MarkedArgumentBuffer args;
306      args.append(propertyName.value(m_globalObject));
307      ASSERT(!args.hasOverflowed());
308      RELEASE_AND_RETURN(scope, call(m_globalObject, asObject(toJSONFunction), callData, baseValue, args));
309  }
310  
311  // We clamp recursion well beyond anything reasonable.
312  constexpr unsigned maximumSideStackRecursion = 40000;
313  Stringifier::StringifyResult Stringifier::appendStringifiedValue(StringBuilder& builder, JSValue value, const Holder& holder, const PropertyNameForFunctionCall& propertyName)
314  {
315      VM& vm = m_globalObject->vm();
316      auto scope = DECLARE_THROW_SCOPE(vm);
317  
318      // Recursion is avoided by !holderStackWasEmpty check and do/while loop at the end of this method.
319      // We're having this recursion check here as a fail safe in case the code
320      // below get modified such that recursion is no longer avoided.
321      if (UNLIKELY(!vm.isSafeToRecurseSoft())) {
322          throwStackOverflowError(m_globalObject, scope);
323          return StringifyFailed;
324      }
325  
326      // Call the toJSON function.
327      if (value.isObject() || value.isBigInt()) {
328          value = toJSON(value, propertyName);
329          RETURN_IF_EXCEPTION(scope, StringifyFailed);
330      }
331  
332      // Call the replacer function.
333      if (isCallableReplacer()) {
334          MarkedArgumentBuffer args;
335          args.append(propertyName.value(m_globalObject));
336          args.append(value);
337          ASSERT(!args.hasOverflowed());
338          ASSERT(holder.object());
339          value = call(m_globalObject, m_replacer, m_replacerCallData, holder.object(), args);
340          RETURN_IF_EXCEPTION(scope, StringifyFailed);
341      }
342  
343      if ((value.isUndefined() || value.isSymbol()) && !holder.isArray())
344          return StringifyFailedDueToUndefinedOrSymbolValue;
345  
346      if (value.isNull()) {
347          builder.appendLiteral("null");
348          return StringifySucceeded;
349      }
350  
351      value = unwrapBoxedPrimitive(m_globalObject, value);
352  
353      RETURN_IF_EXCEPTION(scope, StringifyFailed);
354  
355      if (value.isBoolean()) {
356          if (value.isTrue())
357              builder.appendLiteral("true");
358          else
359              builder.appendLiteral("false");
360          return StringifySucceeded;
361      }
362  
363      if (value.isString()) {
364          const String& string = asString(value)->value(m_globalObject);
365          RETURN_IF_EXCEPTION(scope, StringifyFailed);
366          builder.appendQuotedJSONString(string);
367          return StringifySucceeded;
368      }
369  
370      if (value.isNumber()) {
371          if (value.isInt32())
372              builder.appendNumber(value.asInt32());
373          else {
374              double number = value.asNumber();
375              if (!std::isfinite(number))
376                  builder.appendLiteral("null");
377              else
378                  builder.appendNumber(number);
379          }
380          return StringifySucceeded;
381      }
382  
383      if (value.isBigInt()) {
384          throwTypeError(m_globalObject, scope, "JSON.stringify cannot serialize BigInt."_s);
385          return StringifyFailed;
386      }
387  
388      if (!value.isObject())
389          return StringifyFailed;
390  
391      JSObject* object = asObject(value);
392      if (object->isCallable(vm)) {
393          if (holder.isArray()) {
394              builder.appendLiteral("null");
395              return StringifySucceeded;
396          }
397          return StringifyFailedDueToUndefinedOrSymbolValue;
398      }
399  
400      if (UNLIKELY(builder.hasOverflowed()))
401          return StringifyFailed;
402  
403      // Handle cycle detection, and put the holder on the stack.
404      for (unsigned i = 0; i < m_holderStack.size(); i++) {
405          if (m_holderStack[i].object() == object) {
406              throwTypeError(m_globalObject, scope, "JSON.stringify cannot serialize cyclic structures."_s);
407              return StringifyFailed;
408          }
409      }
410  
411      if (UNLIKELY(m_holderStack.size() >= maximumSideStackRecursion)) {
412          throwStackOverflowError(m_globalObject, scope);
413          return StringifyFailed;
414      }
415  
416      bool holderStackWasEmpty = m_holderStack.isEmpty();
417      m_holderStack.append(Holder(m_globalObject, object));
418      m_objectStack.appendWithCrashOnOverflow(object);
419      RETURN_IF_EXCEPTION(scope, StringifyFailed);
420      if (!holderStackWasEmpty)
421          return StringifySucceeded;
422  
423      do {
424          while (m_holderStack.last().appendNextProperty(*this, builder))
425              RETURN_IF_EXCEPTION(scope, StringifyFailed);
426          RETURN_IF_EXCEPTION(scope, StringifyFailed);
427          if (UNLIKELY(builder.hasOverflowed()))
428              return StringifyFailed;
429          m_holderStack.removeLast();
430          m_objectStack.removeLast();
431      } while (!m_holderStack.isEmpty());
432      return StringifySucceeded;
433  }
434  
435  inline bool Stringifier::willIndent() const
436  {
437      return !m_gap.isEmpty();
438  }
439  
440  inline void Stringifier::indent()
441  {
442      // Use a single shared string, m_repeatedGap, so we don't keep allocating new ones as we indent and unindent.
443      unsigned newSize = m_indent.length() + m_gap.length();
444      if (newSize > m_repeatedGap.length())
445          m_repeatedGap = makeString(m_repeatedGap, m_gap);
446      ASSERT(newSize <= m_repeatedGap.length());
447      m_indent = m_repeatedGap.substringSharingImpl(0, newSize);
448  }
449  
450  inline void Stringifier::unindent()
451  {
452      ASSERT(m_indent.length() >= m_gap.length());
453      m_indent = m_repeatedGap.substringSharingImpl(0, m_indent.length() - m_gap.length());
454  }
455  
456  inline void Stringifier::startNewLine(StringBuilder& builder) const
457  {
458      if (m_gap.isEmpty())
459          return;
460      builder.append('\n');
461      builder.append(m_indent);
462  }
463  
464  inline Stringifier::Holder::Holder(JSGlobalObject* globalObject, JSObject* object)
465      : m_object(object)
466      , m_isJSArray(isJSArray(object))
467      , m_isArray(JSC::isArray(globalObject, object))
468  {
469  }
470  
471  inline Stringifier::Holder::Holder(RootHolderTag, JSObject* object)
472      : m_object(object)
473      , m_isJSArray(false)
474      , m_isArray(false)
475  {
476  }
477  
478  bool Stringifier::Holder::appendNextProperty(Stringifier& stringifier, StringBuilder& builder)
479  {
480      ASSERT(m_index <= m_size);
481  
482      JSGlobalObject* globalObject = stringifier.m_globalObject;
483      VM& vm = globalObject->vm();
484      auto scope = DECLARE_THROW_SCOPE(vm);
485  
486      // First time through, initialize.
487      if (!m_index) {
488          if (m_isArray) {
489              uint64_t length = static_cast<uint64_t>(toLength(globalObject, m_object));
490              RETURN_IF_EXCEPTION(scope, false);
491              if (UNLIKELY(length > std::numeric_limits<uint32_t>::max())) {
492                  throwOutOfMemoryError(globalObject, scope);
493                  return false;
494              }
495              m_size = static_cast<uint32_t>(length);
496              RETURN_IF_EXCEPTION(scope, false);
497              builder.append('[');
498          } else {
499              if (stringifier.m_usingArrayReplacer)
500                  m_propertyNames = stringifier.m_arrayReplacerPropertyNames.data();
501              else {
502                  PropertyNameArray objectPropertyNames(vm, PropertyNameMode::Strings, PrivateSymbolMode::Exclude);
503                  m_object->methodTable(vm)->getOwnPropertyNames(m_object, globalObject, objectPropertyNames, DontEnumPropertiesMode::Exclude);
504                  RETURN_IF_EXCEPTION(scope, false);
505                  m_propertyNames = objectPropertyNames.releaseData();
506              }
507              m_size = m_propertyNames->propertyNameVector().size();
508              builder.append('{');
509          }
510          stringifier.indent();
511      }
512      if (UNLIKELY(builder.hasOverflowed()))
513          return false;
514  
515      // Last time through, finish up and return false.
516      if (m_index == m_size) {
517          stringifier.unindent();
518          if (m_size && builder[builder.length() - 1] != '{')
519              stringifier.startNewLine(builder);
520          builder.append(m_isArray ? ']' : '}');
521          return false;
522      }
523  
524      // Handle a single element of the array or object.
525      unsigned index = m_index++;
526      unsigned rollBackPoint = 0;
527      StringifyResult stringifyResult;
528      if (m_isArray) {
529          // Get the value.
530          JSValue value;
531          if (m_isJSArray && m_object->canGetIndexQuickly(index))
532              value = m_object->getIndexQuickly(index);
533          else {
534              value = m_object->get(globalObject, index);
535              RETURN_IF_EXCEPTION(scope, false);
536          }
537  
538          // Append the separator string.
539          if (index)
540              builder.append(',');
541          stringifier.startNewLine(builder);
542  
543          // Append the stringified value.
544          stringifyResult = stringifier.appendStringifiedValue(builder, value, *this, index);
545          ASSERT(stringifyResult != StringifyFailedDueToUndefinedOrSymbolValue);
546      } else {
547          // Get the value.
548          Identifier& propertyName = m_propertyNames->propertyNameVector()[index];
549          JSValue value = m_object->get(globalObject, propertyName);
550          RETURN_IF_EXCEPTION(scope, false);
551  
552          rollBackPoint = builder.length();
553  
554          // Append the separator string.
555          if (builder[rollBackPoint - 1] != '{')
556              builder.append(',');
557          stringifier.startNewLine(builder);
558  
559          // Append the property name.
560          builder.appendQuotedJSONString(propertyName.string());
561          builder.append(':');
562          if (stringifier.willIndent())
563              builder.append(' ');
564  
565          // Append the stringified value.
566          stringifyResult = stringifier.appendStringifiedValue(builder, value, *this, propertyName);
567      }
568      RETURN_IF_EXCEPTION(scope, false);
569  
570      // From this point on, no access to the this pointer or to any members, because the
571      // Holder object may have moved if the call to stringify pushed a new Holder onto
572      // m_holderStack.
573  
574      switch (stringifyResult) {
575          case StringifyFailed:
576              builder.appendLiteral("null");
577              break;
578          case StringifySucceeded:
579              break;
580          case StringifyFailedDueToUndefinedOrSymbolValue:
581              // This only occurs when get an undefined value or a symbol value for
582              // an object property. In this case we don't want the separator and
583              // property name that we already appended, so roll back.
584              builder.resize(rollBackPoint);
585              break;
586      }
587  
588      return true;
589  }
590  
591  // ------------------------------ JSONObject --------------------------------
592  
593  const ClassInfo JSONObject::s_info = { "JSON", &JSNonFinalObject::s_info, &jsonTable, nullptr, CREATE_METHOD_TABLE(JSONObject) };
594  
595  /* Source for JSONObject.lut.h
596  @begin jsonTable
597    parse         JSONProtoFuncParse             DontEnum|Function 2
598    stringify     JSONProtoFuncStringify         DontEnum|Function 3
599  @end
600  */
601  
602  // ECMA 15.8
603  
604  class Walker {
605      WTF_MAKE_NONCOPYABLE(Walker);
606      WTF_FORBID_HEAP_ALLOCATION;
607  public:
608      Walker(JSGlobalObject* globalObject, JSObject* function, CallData callData)
609          : m_globalObject(globalObject)
610          , m_function(function)
611          , m_callData(callData)
612      {
613      }
614      JSValue walk(JSValue unfiltered);
615  private:
616      JSValue callReviver(JSObject* thisObj, JSValue property, JSValue unfiltered)
617      {
618          MarkedArgumentBuffer args;
619          args.append(property);
620          args.append(unfiltered);
621          ASSERT(!args.hasOverflowed());
622          return call(m_globalObject, m_function, m_callData, thisObj, args);
623      }
624  
625      friend class Holder;
626  
627      JSGlobalObject* m_globalObject;
628      JSObject* m_function;
629      CallData m_callData;
630  };
631  
632  enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember, 
633                                   ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
634  NEVER_INLINE JSValue Walker::walk(JSValue unfiltered)
635  {
636      VM& vm = m_globalObject->vm();
637      auto scope = DECLARE_THROW_SCOPE(vm);
638  
639      Vector<PropertyNameArray, 16, UnsafeVectorOverflow> propertyStack;
640      Vector<uint32_t, 16, UnsafeVectorOverflow> indexStack;
641      MarkedArgumentBuffer markedStack;
642      Vector<unsigned, 16, UnsafeVectorOverflow> arrayLengthStack;
643      
644      Vector<WalkerState, 16, UnsafeVectorOverflow> stateStack;
645      WalkerState state = StateUnknown;
646      JSValue inValue = unfiltered;
647      JSValue outValue = jsNull();
648      
649      while (1) {
650          switch (state) {
651              arrayStartState:
652              case ArrayStartState: {
653                  ASSERT(inValue.isObject());
654                  ASSERT(isArray(m_globalObject, inValue));
655                  EXCEPTION_ASSERT(!scope.exception());
656  
657                  if (UNLIKELY(markedStack.size() >= maximumSideStackRecursion))
658                      return throwStackOverflowError(m_globalObject, scope);
659  
660                  JSObject* array = asObject(inValue);
661                  markedStack.appendWithCrashOnOverflow(array);
662                  uint64_t length = static_cast<uint64_t>(toLength(m_globalObject, array));
663                  RETURN_IF_EXCEPTION(scope, { });
664                  if (UNLIKELY(length > std::numeric_limits<uint32_t>::max())) {
665                      throwOutOfMemoryError(m_globalObject, scope);
666                      return { };
667                  }
668                  RETURN_IF_EXCEPTION(scope, { });
669                  arrayLengthStack.append(static_cast<uint32_t>(length));
670                  indexStack.append(0);
671              }
672              arrayStartVisitMember:
673              FALLTHROUGH;
674              case ArrayStartVisitMember: {
675                  JSObject* array = asObject(markedStack.last());
676                  uint32_t index = indexStack.last();
677                  unsigned arrayLength = arrayLengthStack.last();
678                  if (index == arrayLength) {
679                      outValue = array;
680                      markedStack.removeLast();
681                      arrayLengthStack.removeLast();
682                      indexStack.removeLast();
683                      break;
684                  }
685                  if (isJSArray(array) && array->canGetIndexQuickly(index))
686                      inValue = array->getIndexQuickly(index);
687                  else {
688                      inValue = array->get(m_globalObject, index);
689                      RETURN_IF_EXCEPTION(scope, { });
690                  }
691  
692                  if (inValue.isObject()) {
693                      stateStack.append(ArrayEndVisitMember);
694                      goto stateUnknown;
695                  } else
696                      outValue = inValue;
697                  FALLTHROUGH;
698              }
699              case ArrayEndVisitMember: {
700                  JSObject* array = asObject(markedStack.last());
701                  JSValue filteredValue = callReviver(array, jsString(vm, String::number(indexStack.last())), outValue);
702                  RETURN_IF_EXCEPTION(scope, { });
703                  if (filteredValue.isUndefined())
704                      array->methodTable(vm)->deletePropertyByIndex(array, m_globalObject, indexStack.last());
705                  else
706                      array->putDirectIndex(m_globalObject, indexStack.last(), filteredValue, 0, PutDirectIndexShouldNotThrow);
707                  RETURN_IF_EXCEPTION(scope, { });
708                  indexStack.last()++;
709                  goto arrayStartVisitMember;
710              }
711              objectStartState:
712              case ObjectStartState: {
713                  ASSERT(inValue.isObject());
714                  ASSERT(!isJSArray(inValue));
715                  if (UNLIKELY(markedStack.size() >= maximumSideStackRecursion))
716                      return throwStackOverflowError(m_globalObject, scope);
717  
718                  JSObject* object = asObject(inValue);
719                  markedStack.appendWithCrashOnOverflow(object);
720                  indexStack.append(0);
721                  propertyStack.append(PropertyNameArray(vm, PropertyNameMode::Strings, PrivateSymbolMode::Exclude));
722                  object->methodTable(vm)->getOwnPropertyNames(object, m_globalObject, propertyStack.last(), DontEnumPropertiesMode::Exclude);
723                  RETURN_IF_EXCEPTION(scope, { });
724              }
725              objectStartVisitMember:
726              FALLTHROUGH;
727              case ObjectStartVisitMember: {
728                  JSObject* object = jsCast<JSObject*>(markedStack.last());
729                  uint32_t index = indexStack.last();
730                  PropertyNameArray& properties = propertyStack.last();
731                  if (index == properties.size()) {
732                      outValue = object;
733                      markedStack.removeLast();
734                      indexStack.removeLast();
735                      propertyStack.removeLast();
736                      break;
737                  }
738                  inValue = object->get(m_globalObject, properties[index]);
739                  // The holder may be modified by the reviver function so any lookup may throw
740                  RETURN_IF_EXCEPTION(scope, { });
741  
742                  if (inValue.isObject()) {
743                      stateStack.append(ObjectEndVisitMember);
744                      goto stateUnknown;
745                  } else
746                      outValue = inValue;
747                  FALLTHROUGH;
748              }
749              case ObjectEndVisitMember: {
750                  JSObject* object = jsCast<JSObject*>(markedStack.last());
751                  Identifier prop = propertyStack.last()[indexStack.last()];
752                  JSValue filteredValue = callReviver(object, jsString(vm, prop.string()), outValue);
753                  RETURN_IF_EXCEPTION(scope, { });
754                  if (filteredValue.isUndefined())
755                      JSCell::deleteProperty(object, m_globalObject, prop);
756                  else {
757                      unsigned attributes;
758                      PropertyOffset offset = object->getDirectOffset(vm, prop, attributes);
759                      if (LIKELY(offset != invalidOffset && attributes == static_cast<unsigned>(PropertyAttribute::None)))
760                          object->putDirect(vm, offset, filteredValue);
761                      else {
762                          PropertyDescriptor descriptor(filteredValue, static_cast<unsigned>(PropertyAttribute::None));
763                          bool shouldThrow = false;
764                          object->methodTable(vm)->defineOwnProperty(object, m_globalObject, prop, descriptor, shouldThrow);
765                      }
766                  }
767                  RETURN_IF_EXCEPTION(scope, { });
768                  indexStack.last()++;
769                  goto objectStartVisitMember;
770              }
771              stateUnknown:
772              case StateUnknown:
773                  if (!inValue.isObject()) {
774                      outValue = inValue;
775                      break;
776                  }
777                  bool valueIsArray = isArray(m_globalObject, inValue);
778                  RETURN_IF_EXCEPTION(scope, { });
779                  if (valueIsArray)
780                      goto arrayStartState;
781                  goto objectStartState;
782          }
783          if (stateStack.isEmpty())
784              break;
785  
786          state = stateStack.last();
787          stateStack.removeLast();
788      }
789      JSObject* finalHolder = constructEmptyObject(m_globalObject);
790      finalHolder->putDirect(vm, vm.propertyNames->emptyIdentifier, outValue);
791      RELEASE_AND_RETURN(scope, callReviver(finalHolder, jsEmptyString(vm), outValue));
792  }
793  
794  // ECMA-262 v5 15.12.2
795  JSC_DEFINE_HOST_FUNCTION(JSONProtoFuncParse, (JSGlobalObject* globalObject, CallFrame* callFrame))
796  {
797      VM& vm = globalObject->vm();
798      auto scope = DECLARE_THROW_SCOPE(vm);
799      auto* string = callFrame->argument(0).toString(globalObject);
800      RETURN_IF_EXCEPTION(scope, { });
801      auto viewWithString = string->viewWithUnderlyingString(globalObject);
802      RETURN_IF_EXCEPTION(scope, { });
803      StringView view = viewWithString.view;
804  
805      JSValue unfiltered;
806      if (view.is8Bit()) {
807          LiteralParser<LChar> jsonParser(globalObject, view.characters8(), view.length(), StrictJSON);
808          unfiltered = jsonParser.tryLiteralParse();
809          EXCEPTION_ASSERT(!scope.exception() || !unfiltered);
810          if (!unfiltered) {
811              RETURN_IF_EXCEPTION(scope, { });
812              return throwVMError(globalObject, scope, createSyntaxError(globalObject, jsonParser.getErrorMessage()));
813          }
814      } else {
815          LiteralParser<UChar> jsonParser(globalObject, view.characters16(), view.length(), StrictJSON);
816          unfiltered = jsonParser.tryLiteralParse();
817          EXCEPTION_ASSERT(!scope.exception() || !unfiltered);
818          if (!unfiltered) {
819              RETURN_IF_EXCEPTION(scope, { });
820              return throwVMError(globalObject, scope, createSyntaxError(globalObject, jsonParser.getErrorMessage()));
821          }
822      }
823      
824      if (callFrame->argumentCount() < 2)
825          return JSValue::encode(unfiltered);
826      
827      JSValue function = callFrame->uncheckedArgument(1);
828      auto callData = getCallData(vm, function);
829      if (callData.type == CallData::Type::None)
830          return JSValue::encode(unfiltered);
831      scope.release();
832      Walker walker(globalObject, asObject(function), callData);
833      return JSValue::encode(walker.walk(unfiltered));
834  }
835  
836  // ECMA-262 v5 15.12.3
837  JSC_DEFINE_HOST_FUNCTION(JSONProtoFuncStringify, (JSGlobalObject* globalObject, CallFrame* callFrame))
838  {
839      VM& vm = globalObject->vm();
840      auto scope = DECLARE_THROW_SCOPE(vm);
841  
842      Stringifier stringifier(globalObject, callFrame->argument(1), callFrame->argument(2));
843      RETURN_IF_EXCEPTION(scope, { });
844      RELEASE_AND_RETURN(scope, JSValue::encode(stringifier.stringify(callFrame->argument(0))));
845  }
846  
847  JSValue JSONParse(JSGlobalObject* globalObject, const String& json)
848  {
849      if (json.isNull())
850          return JSValue();
851  
852      if (json.is8Bit()) {
853          LiteralParser<LChar> jsonParser(globalObject, json.characters8(), json.length(), StrictJSON);
854          return jsonParser.tryLiteralParse();
855      }
856  
857      LiteralParser<UChar> jsonParser(globalObject, json.characters16(), json.length(), StrictJSON);
858      return jsonParser.tryLiteralParse();
859  }
860  
861  String JSONStringify(JSGlobalObject* globalObject, JSValue value, JSValue space)
862  {
863      VM& vm = globalObject->vm();
864      auto throwScope = DECLARE_THROW_SCOPE(vm);
865      Stringifier stringifier(globalObject, jsNull(), space);
866      RETURN_IF_EXCEPTION(throwScope, { });
867      JSValue result = stringifier.stringify(value);
868      if (UNLIKELY(throwScope.exception()) || result.isUndefinedOrNull())
869          return String();
870      return result.getString(globalObject);
871  }
872  
873  String JSONStringify(JSGlobalObject* globalObject, JSValue value, unsigned indent)
874  {
875      return JSONStringify(globalObject, value, jsNumber(indent));
876  }
877  
878  } // namespace JSC