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