runtime/JSONObject.cpp

   1 /*
   2  * Copyright (C) 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "JSONObject.h"
  28
  29 #include "BooleanObject.h"
  30 #include "Error.h"
  31 #include "ExceptionHelpers.h"
  32 #include "JSArray.h"
  33 #include "JSGlobalObject.h"
  34 #include "LiteralParser.h"
  35 #include "Local.h"
  36 #include "LocalScope.h"
  37 #include "Lookup.h"
  38 #include "PropertyNameArray.h"
  39 #include "UStringBuilder.h"
  40 #include "UStringConcatenate.h"
  41 #include <wtf/MathExtras.h>
  42
  43 namespace JSC {
  44
  45 ASSERT_CLASS_FITS_IN_CELL(JSONObject);
  46 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&, UStringBuilder&);
  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(UStringBuilder&, const UString&);
 111
 112     JSValue toJSON(JSValue, const PropertyNameForFunctionCall&);
 113
 114     enum StringifyResult { StringifyFailed, StringifySucceeded, StringifyFailedDueToUndefinedValue };
 115     StringifyResult appendStringifiedValue(UStringBuilder&, JSValue, JSObject* holder, const PropertyNameForFunctionCall&);
 116
 117     bool willIndent() const;
 118     void indent();
 119     void unindent();
 120     void startNewLine(UStringBuilder&) 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 UString m_gap;
 129
 130     Vector<Holder, 16> m_holderStack;
 131     UString m_repeatedGap;
 132     UString 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 UString 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 UString(spaces, count);
 170     }
 171
 172     // If the space value is a string, use it as the gap string, otherwise use no gap string.
 173     UString 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->ustring());
 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     UStringBuilder 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.toUString()));
 255 }
 256
 257 template <typename CharType>
 258 static void appendStringToUStringBuilder(UStringBuilder& 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', hexDigits[(ch >> 12) & 0xF], hexDigits[(ch >> 8) & 0xF], hexDigits[(ch >> 4) & 0xF], hexDigits[ch & 0xF] };
 300             builder.append(hex, WTF_ARRAY_LENGTH(hex));
 301             break;
 302         }
 303     }
 304 }
 305
 306 void Stringifier::appendQuotedString(UStringBuilder& builder, const UString& value)
 307 {
 308     int length = value.length();
 309
 310     builder.append('"');
 311
 312     if (value.is8Bit())
 313         appendStringToUStringBuilder<LChar>(builder, value.characters8(), length);
 314     else
 315         appendStringToUStringBuilder<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(UStringBuilder& builder, JSValue value, JSObject* holder, const PropertyNameForFunctionCall& propertyName)
 345 {
 346     // Call the toJSON function.
 347     value = toJSON(value, propertyName);
 348     if (m_exec->hadException())
 349         return StringifyFailed;
 350
 351     // Call the replacer function.
 352     if (m_replacerCallType != CallTypeNone) {
 353         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.append("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         builder.append(value.isTrue() ? "true" : "false");
 376         return StringifySucceeded;
 377     }
 378
 379     UString stringValue;
 380     if (value.getString(m_exec, stringValue)) {
 381         appendQuotedString(builder, stringValue);
 382         return StringifySucceeded;
 383     }
 384
 385     if (value.isNumber()) {
 386         double number = value.asNumber();
 387         if (!isfinite(number))
 388             builder.append("null");
 389         else
 390             builder.append(UString::number(number));
 391         return StringifySucceeded;
 392     }
 393
 394     if (!value.isObject())
 395         return StringifyFailed;
 396
 397     JSObject* object = asObject(value);
 398
 399     CallData callData;
 400     if (object->methodTable()->getCallData(object, callData) != CallTypeNone) {
 401         if (holder->inherits(&JSArray::s_info)) {
 402             builder.append("null");
 403             return StringifySucceeded;
 404         }
 405         return StringifyFailedDueToUndefinedValue;
 406     }
 407
 408     // Handle cycle detection, and put the holder on the stack.
 409     for (unsigned i = 0; i < m_holderStack.size(); i++) {
 410         if (m_holderStack[i].object() == object) {
 411             throwError(m_exec, createTypeError(m_exec, "JSON.stringify cannot serialize cyclic structures."));
 412             return StringifyFailed;
 413         }
 414     }
 415     bool holderStackWasEmpty = m_holderStack.isEmpty();
 416     m_holderStack.append(Holder(m_exec->globalData(), object));
 417     if (!holderStackWasEmpty)
 418         return StringifySucceeded;
 419
 420     // If this is the outermost call, then loop to handle everything on the holder stack.
 421     TimeoutChecker localTimeoutChecker(m_exec->globalData().timeoutChecker);
 422     localTimeoutChecker.reset();
 423     unsigned tickCount = localTimeoutChecker.ticksUntilNextCheck();
 424     do {
 425         while (m_holderStack.last().appendNextProperty(*this, builder)) {
 426             if (m_exec->hadException())
 427                 return StringifyFailed;
 428             if (!--tickCount) {
 429                 if (localTimeoutChecker.didTimeOut(m_exec)) {
 430                     throwError(m_exec, createInterruptedExecutionException(&m_exec->globalData()));
 431                     return StringifyFailed;
 432                 }
 433                 tickCount = localTimeoutChecker.ticksUntilNextCheck();
 434             }
 435         }
 436         m_holderStack.removeLast();
 437     } while (!m_holderStack.isEmpty());
 438     return StringifySucceeded;
 439 }
 440
 441 inline bool Stringifier::willIndent() const
 442 {
 443     return !m_gap.isEmpty();
 444 }
 445
 446 inline void Stringifier::indent()
 447 {
 448     // Use a single shared string, m_repeatedGap, so we don't keep allocating new ones as we indent and unindent.
 449     unsigned newSize = m_indent.length() + m_gap.length();
 450     if (newSize > m_repeatedGap.length())
 451         m_repeatedGap = makeUString(m_repeatedGap, m_gap);
 452     ASSERT(newSize <= m_repeatedGap.length());
 453     m_indent = m_repeatedGap.substringSharingImpl(0, newSize);
 454 }
 455
 456 inline void Stringifier::unindent()
 457 {
 458     ASSERT(m_indent.length() >= m_gap.length());
 459     m_indent = m_repeatedGap.substringSharingImpl(0, m_indent.length() - m_gap.length());
 460 }
 461
 462 inline void Stringifier::startNewLine(UStringBuilder& builder) const
 463 {
 464     if (m_gap.isEmpty())
 465         return;
 466     builder.append('\n');
 467     builder.append(m_indent);
 468 }
 469
 470 inline Stringifier::Holder::Holder(JSGlobalData& globalData, JSObject* object)
 471     : m_object(globalData, object)
 472     , m_isArray(object->inherits(&JSArray::s_info))
 473     , m_index(0)
 474 {
 475 }
 476
 477 bool Stringifier::Holder::appendNextProperty(Stringifier& stringifier, UStringBuilder& builder)
 478 {
 479     ASSERT(m_index <= m_size);
 480
 481     ExecState* exec = stringifier.m_exec;
 482
 483     // First time through, initialize.
 484     if (!m_index) {
 485         if (m_isArray) {
 486             m_isJSArray = isJSArray(m_object.get());
 487             m_size = m_object->get(exec, exec->globalData().propertyNames->length).toUInt32(exec);
 488             builder.append('[');
 489         } else {
 490             if (stringifier.m_usingArrayReplacer)
 491                 m_propertyNames = stringifier.m_arrayReplacerPropertyNames.data();
 492             else {
 493                 PropertyNameArray objectPropertyNames(exec);
 494                 m_object->methodTable()->getOwnPropertyNames(m_object.get(), exec, objectPropertyNames, ExcludeDontEnumProperties);
 495                 m_propertyNames = objectPropertyNames.releaseData();
 496             }
 497             m_size = m_propertyNames->propertyNameVector().size();
 498             builder.append('{');
 499         }
 500         stringifier.indent();
 501     }
 502
 503     // Last time through, finish up and return false.
 504     if (m_index == m_size) {
 505         stringifier.unindent();
 506         if (m_size && builder[builder.length() - 1] != '{')
 507             stringifier.startNewLine(builder);
 508         builder.append(m_isArray ? ']' : '}');
 509         return false;
 510     }
 511
 512     // Handle a single element of the array or object.
 513     unsigned index = m_index++;
 514     unsigned rollBackPoint = 0;
 515     StringifyResult stringifyResult;
 516     if (m_isArray) {
 517         // Get the value.
 518         JSValue value;
 519         if (m_isJSArray && asArray(m_object.get())->canGetIndex(index))
 520             value = asArray(m_object.get())->getIndex(index);
 521         else {
 522             PropertySlot slot(m_object.get());
 523             if (!m_object->methodTable()->getOwnPropertySlotByIndex(m_object.get(), exec, index, slot))
 524                 slot.setUndefined();
 525             if (exec->hadException())
 526                 return false;
 527             value = slot.getValue(exec, index);
 528         }
 529
 530         // Append the separator string.
 531         if (index)
 532             builder.append(',');
 533         stringifier.startNewLine(builder);
 534
 535         // Append the stringified value.
 536         stringifyResult = stringifier.appendStringifiedValue(builder, value, m_object.get(), index);
 537     } else {
 538         // Get the value.
 539         PropertySlot slot(m_object.get());
 540         Identifier& propertyName = m_propertyNames->propertyNameVector()[index];
 541         if (!m_object->methodTable()->getOwnPropertySlot(m_object.get(), exec, propertyName, slot))
 542             return true;
 543         JSValue value = slot.getValue(exec, propertyName);
 544         if (exec->hadException())
 545             return false;
 546
 547         rollBackPoint = builder.length();
 548
 549         // Append the separator string.
 550         if (builder[rollBackPoint - 1] != '{')
 551             builder.append(',');
 552         stringifier.startNewLine(builder);
 553
 554         // Append the property name.
 555         appendQuotedString(builder, propertyName.ustring());
 556         builder.append(':');
 557         if (stringifier.willIndent())
 558             builder.append(' ');
 559
 560         // Append the stringified value.
 561         stringifyResult = stringifier.appendStringifiedValue(builder, value, m_object.get(), propertyName);
 562     }
 563
 564     // From this point on, no access to the this pointer or to any members, because the
 565     // Holder object may have moved if the call to stringify pushed a new Holder onto
 566     // m_holderStack.
 567
 568     switch (stringifyResult) {
 569         case StringifyFailed:
 570             builder.append("null");
 571             break;
 572         case StringifySucceeded:
 573             break;
 574         case StringifyFailedDueToUndefinedValue:
 575             // This only occurs when get an undefined value for an object property.
 576             // In this case we don't want the separator and property name that we
 577             // already appended, so roll back.
 578             builder.resize(rollBackPoint);
 579             break;
 580     }
 581
 582     return true;
 583 }
 584
 585 // ------------------------------ JSONObject --------------------------------
 586
 587 const ClassInfo JSONObject::s_info = { "JSON", &JSNonFinalObject::s_info, 0, ExecState::jsonTable, CREATE_METHOD_TABLE(JSONObject) };
 588
 589 /* Source for JSONObject.lut.h
 590 @begin jsonTable
 591   parse         JSONProtoFuncParse             DontEnum|Function 2
 592   stringify     JSONProtoFuncStringify         DontEnum|Function 3
 593 @end
 594 */
 595
 596 // ECMA 15.8
 597
 598 bool JSONObject::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 599 {
 600     return getStaticFunctionSlot<JSObject>(exec, ExecState::jsonTable(exec), jsCast<JSONObject*>(cell), propertyName, slot);
 601 }
 602
 603 bool JSONObject::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
 604 {
 605     return getStaticFunctionDescriptor<JSObject>(exec, ExecState::jsonTable(exec), jsCast<JSONObject*>(object), propertyName, descriptor);
 606 }
 607
 608 class Walker {
 609 public:
 610     Walker(ExecState* exec, Handle<JSObject> function, CallType callType, CallData callData)
 611         : m_exec(exec)
 612         , m_function(exec->globalData(), function)
 613         , m_callType(callType)
 614         , m_callData(callData)
 615     {
 616     }
 617     JSValue walk(JSValue unfiltered);
 618 private:
 619     JSValue callReviver(JSObject* thisObj, JSValue property, JSValue unfiltered)
 620     {
 621         MarkedArgumentBuffer args;
 622         args.append(property);
 623         args.append(unfiltered);
 624         return call(m_exec, m_function.get(), m_callType, m_callData, thisObj, args);
 625     }
 626
 627     friend class Holder;
 628
 629     ExecState* m_exec;
 630     Local<JSObject> m_function;
 631     CallType m_callType;
 632     CallData m_callData;
 633 };
 634
 635 // We clamp recursion well beyond anything reasonable, but we also have a timeout check
 636 // to guard against "infinite" execution by inserting arbitrarily large objects.
 637 static const unsigned maximumFilterRecursion = 40000;
 638 enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember,
 639                                  ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
 640 NEVER_INLINE JSValue Walker::walk(JSValue unfiltered)
 641 {
 642     Vector<PropertyNameArray, 16> propertyStack;
 643     Vector<uint32_t, 16> indexStack;
 644     LocalStack<JSObject, 16> objectStack(m_exec->globalData());
 645     LocalStack<JSArray, 16> arrayStack(m_exec->globalData());
 646
 647     Vector<WalkerState, 16> stateStack;
 648     WalkerState state = StateUnknown;
 649     JSValue inValue = unfiltered;
 650     JSValue outValue = jsNull();
 651
 652     TimeoutChecker localTimeoutChecker(m_exec->globalData().timeoutChecker);
 653     localTimeoutChecker.reset();
 654     unsigned tickCount = localTimeoutChecker.ticksUntilNextCheck();
 655     while (1) {
 656         switch (state) {
 657             arrayStartState:
 658             case ArrayStartState: {
 659                 ASSERT(inValue.isObject());
 660                 ASSERT(isJSArray(asObject(inValue)) || asObject(inValue)->inherits(&JSArray::s_info));
 661                 if (objectStack.size() + arrayStack.size() > maximumFilterRecursion)
 662                     return throwError(m_exec, createStackOverflowError(m_exec));
 663
 664                 JSArray* array = asArray(inValue);
 665                 arrayStack.push(array);
 666                 indexStack.append(0);
 667                 // fallthrough
 668             }
 669             arrayStartVisitMember:
 670             case ArrayStartVisitMember: {
 671                 if (!--tickCount) {
 672                     if (localTimeoutChecker.didTimeOut(m_exec))
 673                         return throwError(m_exec, createInterruptedExecutionException(&m_exec->globalData()));
 674                     tickCount = localTimeoutChecker.ticksUntilNextCheck();
 675                 }
 676
 677                 JSArray* array = arrayStack.peek();
 678                 uint32_t index = indexStack.last();
 679                 if (index == array->length()) {
 680                     outValue = array;
 681                     arrayStack.pop();
 682                     indexStack.removeLast();
 683                     break;
 684                 }
 685                 if (isJSArray(array) && array->canGetIndex(index))
 686                     inValue = array->getIndex(index);
 687                 else {
 688                     PropertySlot slot;
 689                     if (array->methodTable()->getOwnPropertySlotByIndex(array, m_exec, index, slot))
 690                         inValue = slot.getValue(m_exec, index);
 691                     else
 692                         inValue = jsUndefined();
 693                 }
 694
 695                 if (inValue.isObject()) {
 696                     stateStack.append(ArrayEndVisitMember);
 697                     goto stateUnknown;
 698                 } else
 699                     outValue = inValue;
 700                 // fallthrough
 701             }
 702             case ArrayEndVisitMember: {
 703                 JSArray* array = arrayStack.peek();
 704                 JSValue filteredValue = callReviver(array, jsString(m_exec, UString::number(indexStack.last())), outValue);
 705                 if (filteredValue.isUndefined())
 706                     array->methodTable()->deletePropertyByIndex(array, m_exec, indexStack.last());
 707                 else
 708                     array->putDirectIndex(m_exec, indexStack.last(), filteredValue, false);
 709                 if (m_exec->hadException())
 710                     return jsNull();
 711                 indexStack.last()++;
 712                 goto arrayStartVisitMember;
 713             }
 714             objectStartState:
 715             case ObjectStartState: {
 716                 ASSERT(inValue.isObject());
 717                 ASSERT(!isJSArray(asObject(inValue)) && !asObject(inValue)->inherits(&JSArray::s_info));
 718                 if (objectStack.size() + arrayStack.size() > maximumFilterRecursion)
 719                     return throwError(m_exec, createStackOverflowError(m_exec));
 720
 721                 JSObject* object = asObject(inValue);
 722                 objectStack.push(object);
 723                 indexStack.append(0);
 724                 propertyStack.append(PropertyNameArray(m_exec));
 725                 object->methodTable()->getOwnPropertyNames(object, m_exec, propertyStack.last(), ExcludeDontEnumProperties);
 726                 // fallthrough
 727             }
 728             objectStartVisitMember:
 729             case ObjectStartVisitMember: {
 730                 if (!--tickCount) {
 731                     if (localTimeoutChecker.didTimeOut(m_exec))
 732                         return throwError(m_exec, createInterruptedExecutionException(&m_exec->globalData()));
 733                     tickCount = localTimeoutChecker.ticksUntilNextCheck();
 734                 }
 735
 736                 JSObject* object = objectStack.peek();
 737                 uint32_t index = indexStack.last();
 738                 PropertyNameArray& properties = propertyStack.last();
 739                 if (index == properties.size()) {
 740                     outValue = object;
 741                     objectStack.pop();
 742                     indexStack.removeLast();
 743                     propertyStack.removeLast();
 744                     break;
 745                 }
 746                 PropertySlot slot;
 747                 if (object->methodTable()->getOwnPropertySlot(object, m_exec, properties[index], slot))
 748                     inValue = slot.getValue(m_exec, properties[index]);
 749                 else
 750                     inValue = jsUndefined();
 751
 752                 // The holder may be modified by the reviver function so any lookup may throw
 753                 if (m_exec->hadException())
 754                     return jsNull();
 755
 756                 if (inValue.isObject()) {
 757                     stateStack.append(ObjectEndVisitMember);
 758                     goto stateUnknown;
 759                 } else
 760                     outValue = inValue;
 761                 // fallthrough
 762             }
 763             case ObjectEndVisitMember: {
 764                 JSObject* object = objectStack.peek();
 765                 Identifier prop = propertyStack.last()[indexStack.last()];
 766                 PutPropertySlot slot;
 767                 JSValue filteredValue = callReviver(object, jsString(m_exec, prop.ustring()), outValue);
 768                 if (filteredValue.isUndefined())
 769                     object->methodTable()->deleteProperty(object, m_exec, prop);
 770                 else
 771                     object->methodTable()->put(object, m_exec, prop, filteredValue, slot);
 772                 if (m_exec->hadException())
 773                     return jsNull();
 774                 indexStack.last()++;
 775                 goto objectStartVisitMember;
 776             }
 777             stateUnknown:
 778             case StateUnknown:
 779                 if (!inValue.isObject()) {
 780                     outValue = inValue;
 781                     break;
 782                 }
 783                 JSObject* object = asObject(inValue);
 784                 if (isJSArray(object) || object->inherits(&JSArray::s_info))
 785                     goto arrayStartState;
 786                 goto objectStartState;
 787         }
 788         if (stateStack.isEmpty())
 789             break;
 790
 791         state = stateStack.last();
 792         stateStack.removeLast();
 793
 794         if (!--tickCount) {
 795             if (localTimeoutChecker.didTimeOut(m_exec))
 796                 return throwError(m_exec, createInterruptedExecutionException(&m_exec->globalData()));
 797             tickCount = localTimeoutChecker.ticksUntilNextCheck();
 798         }
 799     }
 800     JSObject* finalHolder = constructEmptyObject(m_exec);
 801     PutPropertySlot slot;
 802     finalHolder->methodTable()->put(finalHolder, m_exec, m_exec->globalData().propertyNames->emptyIdentifier, outValue, slot);
 803     return callReviver(finalHolder, jsEmptyString(m_exec), outValue);
 804 }
 805
 806 // ECMA-262 v5 15.12.2
 807 EncodedJSValue JSC_HOST_CALL JSONProtoFuncParse(ExecState* exec)
 808 {
 809     if (!exec->argumentCount())
 810         return throwVMError(exec, createError(exec, "JSON.parse requires at least one parameter"));
 811     UString source = exec->argument(0).toString(exec)->value(exec);
 812     if (exec->hadException())
 813         return JSValue::encode(jsNull());
 814
 815     JSValue unfiltered;
 816     LocalScope scope(exec->globalData());
 817     if (source.is8Bit()) {
 818         LiteralParser<LChar> jsonParser(exec, source.characters8(), source.length(), StrictJSON);
 819         unfiltered = jsonParser.tryLiteralParse();
 820         if (!unfiltered)
 821             return throwVMError(exec, createSyntaxError(exec, jsonParser.getErrorMessage()));
 822     } else {
 823         LiteralParser<UChar> jsonParser(exec, source.characters16(), source.length(), StrictJSON);
 824         unfiltered = jsonParser.tryLiteralParse();
 825         if (!unfiltered)
 826             return throwVMError(exec, createSyntaxError(exec, jsonParser.getErrorMessage()));
 827     }
 828
 829     if (exec->argumentCount() < 2)
 830         return JSValue::encode(unfiltered);
 831
 832     JSValue function = exec->argument(1);
 833     CallData callData;
 834     CallType callType = getCallData(function, callData);
 835     if (callType == CallTypeNone)
 836         return JSValue::encode(unfiltered);
 837     return JSValue::encode(Walker(exec, Local<JSObject>(exec->globalData(), asObject(function)), callType, callData).walk(unfiltered));
 838 }
 839
 840 // ECMA-262 v5 15.12.3
 841 EncodedJSValue JSC_HOST_CALL JSONProtoFuncStringify(ExecState* exec)
 842 {
 843     if (!exec->argumentCount())
 844         return throwVMError(exec, createError(exec, "No input to stringify"));
 845     LocalScope scope(exec->globalData());
 846     Local<Unknown> value(exec->globalData(), exec->argument(0));
 847     Local<Unknown> replacer(exec->globalData(), exec->argument(1));
 848     Local<Unknown> space(exec->globalData(), exec->argument(2));
 849     return JSValue::encode(Stringifier(exec, replacer, space).stringify(value).get());
 850 }
 851
 852 UString JSONStringify(ExecState* exec, JSValue value, unsigned indent)
 853 {
 854     LocalScope scope(exec->globalData());
 855     Local<Unknown> result = Stringifier(exec, Local<Unknown>(exec->globalData(), jsNull()), Local<Unknown>(exec->globalData(), jsNumber(indent))).stringify(Local<Unknown>(exec->globalData(), value));
 856     if (result.isUndefinedOrNull())
 857         return UString();
 858     return result.getString(exec);
 859 }
 860
 861 } // namespace JSC