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