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