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