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