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 "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.release());
 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