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