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