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