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