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