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