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