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