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