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