WebCore/bindings/js/SerializedScriptValue.cpp - platform/external/webkit - Git at Google

 /*
  * Copyright (C) 2009 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  */

 #include "config.h"
 #include "SerializedScriptValue.h"

 #include <runtime/DateInstance.h>
 #include <runtime/ExceptionHelpers.h>
 #include <runtime/PropertyNameArray.h>
 #include <wtf/HashTraits.h>
 #include <wtf/Vector.h>

 using namespace JSC;

 namespace WebCore {

 class SerializedObject : public SharedSerializedData
 {
 public:
     typedef Vector<RefPtr<StringImpl> > PropertyNameList;
     typedef Vector<SerializedScriptValueData> ValueList;

     void set(const Identifier& propertyName, const SerializedScriptValueData& value)
     {
         ASSERT(m_names.size() == m_values.size());
         m_names.append(String(propertyName.ustring()).crossThreadString().impl());
         m_values.append(value);
     }

     PropertyNameList& names() { return m_names; }

     ValueList& values() { return m_values; }

     static PassRefPtr<SerializedObject> create()
     {
         return adoptRef(new SerializedObject);
     }

     void clear()
     {
         m_names.clear();
         m_values.clear();
     }

 private:
     SerializedObject() { }
     PropertyNameList m_names;
     ValueList m_values;
 };

 class SerializedArray : public SharedSerializedData
 {
     typedef HashMap<unsigned, SerializedScriptValueData, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned> > SparseMap;
 public:
     void setIndex(unsigned index, const SerializedScriptValueData& value)
     {
         ASSERT(index < m_length);
         if (index == m_compactStorage.size())
             m_compactStorage.append(value);
         else
             m_sparseStorage.set(index, value);
     }

     bool canDoFastRead(unsigned index) const
     {
         ASSERT(index < m_length);
         return index < m_compactStorage.size();
     }

     const SerializedScriptValueData& getIndex(unsigned index)
     {
         ASSERT(index < m_compactStorage.size());
         return m_compactStorage[index];
     }

     SerializedScriptValueData getSparseIndex(unsigned index, bool& hasIndex)
     {
         ASSERT(index >= m_compactStorage.size());
         ASSERT(index < m_length);
         SparseMap::iterator iter = m_sparseStorage.find(index);
         if (iter == m_sparseStorage.end()) {
             hasIndex = false;
             return SerializedScriptValueData();
         }
         hasIndex = true;
         return iter->second;
     }

     unsigned length() const
     {
         return m_length;
     }

     static PassRefPtr<SerializedArray> create(unsigned length)
     {
         return adoptRef(new SerializedArray(length));
     }

     void clear()
     {
         m_compactStorage.clear();
         m_sparseStorage.clear();
         m_length = 0;
     }
 private:
     SerializedArray(unsigned length)
         : m_length(length)
     {
     }

     Vector<SerializedScriptValueData> m_compactStorage;
     SparseMap m_sparseStorage;
     unsigned m_length;
 };

 SerializedScriptValueData::SerializedScriptValueData(RefPtr<SerializedObject> data)
     : m_type(ObjectType)
     , m_sharedData(data)
 {
 }

 SerializedScriptValueData::SerializedScriptValueData(RefPtr<SerializedArray> data)
     : m_type(ArrayType)
     , m_sharedData(data)
 {
 }

 SerializedArray* SharedSerializedData::asArray()
 {
     return static_cast<SerializedArray*>(this);
 }

 SerializedObject* SharedSerializedData::asObject()
 {
     return static_cast<SerializedObject*>(this);
 }

 static const unsigned maximumFilterRecursion = 40000;
 enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember,
     ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
 template <typename TreeWalker> typename TreeWalker::OutputType walk(TreeWalker& context, typename TreeWalker::InputType in)
 {
     typedef typename TreeWalker::InputObject InputObject;
     typedef typename TreeWalker::InputArray InputArray;
     typedef typename TreeWalker::OutputObject OutputObject;
     typedef typename TreeWalker::OutputArray OutputArray;
     typedef typename TreeWalker::InputType InputType;
     typedef typename TreeWalker::OutputType OutputType;
     typedef typename TreeWalker::PropertyList PropertyList;

     Vector<uint32_t, 16> indexStack;
     Vector<uint32_t, 16> lengthStack;
     Vector<PropertyList, 16> propertyStack;
     Vector<InputObject, 16> inputObjectStack;
     Vector<InputArray, 16> inputArrayStack;
     Vector<OutputObject, 16> outputObjectStack;
     Vector<OutputArray, 16> outputArrayStack;
     Vector<WalkerState, 16> stateStack;
     WalkerState state = StateUnknown;
     InputType inValue = in;
     OutputType outValue = context.null();

     unsigned tickCount = context.ticksUntilNextCheck();
     while (1) {
         switch (state) {
             arrayStartState:
             case ArrayStartState: {
                 ASSERT(context.isArray(inValue));
                 if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion) {
                     context.throwStackOverflow();
                     return context.null();
                 }

                 InputArray inArray = context.asInputArray(inValue);
                 unsigned length = context.length(inArray);
                 OutputArray outArray = context.createOutputArray(length);
                 if (!context.startArray(inArray, outArray))
                     return context.null();
                 inputArrayStack.append(inArray);
                 outputArrayStack.append(outArray);
                 indexStack.append(0);
                 lengthStack.append(length);
                 // fallthrough
             }
             arrayStartVisitMember:
             case ArrayStartVisitMember: {
                 if (!--tickCount) {
                     if (context.didTimeOut()) {
                         context.throwInterruptedException();
                         return context.null();
                     }
                     tickCount = context.ticksUntilNextCheck();
                 }

                 InputArray array = inputArrayStack.last();
                 uint32_t index = indexStack.last();
                 if (index == lengthStack.last()) {
                     InputArray inArray = inputArrayStack.last();
                     OutputArray outArray = outputArrayStack.last();
                     context.endArray(inArray, outArray);
                     outValue = outArray;
                     inputArrayStack.removeLast();
                     outputArrayStack.removeLast();
                     indexStack.removeLast();
                     lengthStack.removeLast();
                     break;
                 }
                 if (context.canDoFastRead(array, index))
                     inValue = context.getIndex(array, index);
                 else {
                     bool hasIndex = false;
                     inValue = context.getSparseIndex(array, index, hasIndex);
                     if (!hasIndex) {
                         indexStack.last()++;
                         goto arrayStartVisitMember;
                     }
                 }

                 if (OutputType transformed = context.convertIfTerminal(inValue))
                     outValue = transformed;
                 else {
                     stateStack.append(ArrayEndVisitMember);
                     goto stateUnknown;
                 }
                 // fallthrough
             }
             case ArrayEndVisitMember: {
                 OutputArray outArray = outputArrayStack.last();
                 context.putProperty(outArray, indexStack.last(), outValue);
                 indexStack.last()++;
                 goto arrayStartVisitMember;
             }
             objectStartState:
             case ObjectStartState: {
                 ASSERT(context.isObject(inValue));
                 if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion) {
                     context.throwStackOverflow();
                     return context.null();
                 }
                 InputObject inObject = context.asInputObject(inValue);
                 OutputObject outObject = context.createOutputObject();
                 if (!context.startObject(inObject, outObject))
                     return context.null();
                 inputObjectStack.append(inObject);
                 outputObjectStack.append(outObject);
                 indexStack.append(0);
                 context.getPropertyNames(inObject, propertyStack);
                 // fallthrough
             }
             objectStartVisitMember:
             case ObjectStartVisitMember: {
                 if (!--tickCount) {
                     if (context.didTimeOut()) {
                         context.throwInterruptedException();
                         return context.null();
                     }
                     tickCount = context.ticksUntilNextCheck();
                 }

                 InputObject object = inputObjectStack.last();
                 uint32_t index = indexStack.last();
                 PropertyList& properties = propertyStack.last();
                 if (index == properties.size()) {
                     InputObject inObject = inputObjectStack.last();
                     OutputObject outObject = outputObjectStack.last();
                     context.endObject(inObject, outObject);
                     outValue = outObject;
                     inputObjectStack.removeLast();
                     outputObjectStack.removeLast();
                     indexStack.removeLast();
                     propertyStack.removeLast();
                     break;
                 }
                 inValue = context.getProperty(object, properties[index], index);

                 if (context.shouldTerminate())
                     return context.null();

                 if (OutputType transformed = context.convertIfTerminal(inValue))
                     outValue = transformed;
                 else {
                     stateStack.append(ObjectEndVisitMember);
                     goto stateUnknown;
                 }
                 // fallthrough
             }
             case ObjectEndVisitMember: {
                 context.putProperty(outputObjectStack.last(), propertyStack.last()[indexStack.last()], outValue);
                 if (context.shouldTerminate())
                     return context.null();

                 indexStack.last()++;
                 goto objectStartVisitMember;
             }
             stateUnknown:
             case StateUnknown:
                 if (OutputType transformed = context.convertIfTerminal(inValue)) {
                     outValue = transformed;
                     break;
                 }
                 if (context.isArray(inValue))
                     goto arrayStartState;
                 goto objectStartState;
         }
         if (stateStack.isEmpty())
             break;

         state = stateStack.last();
         stateStack.removeLast();

         if (!--tickCount) {
             if (context.didTimeOut()) {
                 context.throwInterruptedException();
                 return context.null();
             }
             tickCount = context.ticksUntilNextCheck();
         }
     }
     return outValue;
 }

 struct BaseWalker {
     BaseWalker(ExecState* exec)
         : m_exec(exec)
         , m_timeoutChecker(exec->globalData().timeoutChecker)
     {
         m_timeoutChecker.reset();
     }
     ExecState* m_exec;
     TimeoutChecker m_timeoutChecker;
     MarkedArgumentBuffer m_gcBuffer;

     bool shouldTerminate()
     {
         return m_exec->hadException();
     }

     unsigned ticksUntilNextCheck()
     {
         return m_timeoutChecker.ticksUntilNextCheck();
     }

     bool didTimeOut()
     {
         return m_timeoutChecker.didTimeOut(m_exec);
     }

     void throwStackOverflow()
     {
         m_exec->setException(createStackOverflowError(m_exec));
     }

     void throwInterruptedException()
     {
         m_exec->setException(createInterruptedExecutionException(&m_exec->globalData()));
     }
 };

 struct SerializingTreeWalker : public BaseWalker {
     typedef JSValue InputType;
     typedef JSArray* InputArray;
     typedef JSObject* InputObject;
     typedef SerializedScriptValueData OutputType;
     typedef RefPtr<SerializedArray> OutputArray;
     typedef RefPtr<SerializedObject> OutputObject;
     typedef PropertyNameArray PropertyList;

     SerializingTreeWalker(ExecState* exec)
         : BaseWalker(exec)
     {
     }

     OutputType null() { return SerializedScriptValueData(); }

     bool isArray(JSValue value)
     {
         if (!value.isObject())
             return false;
         JSObject* object = asObject(value);
         return isJSArray(&m_exec->globalData(), object) || object->inherits(&JSArray::info);
     }

     bool isObject(JSValue value)
     {
         return value.isObject();
     }

     JSArray* asInputArray(JSValue value)
     {
         return asArray(value);
     }

     JSObject* asInputObject(JSValue value)
     {
         return asObject(value);
     }

     PassRefPtr<SerializedArray> createOutputArray(unsigned length)
     {
         return SerializedArray::create(length);
     }

     PassRefPtr<SerializedObject> createOutputObject()
     {
         return SerializedObject::create();
     }

     uint32_t length(JSValue array)
     {
         ASSERT(array.isObject());
         JSObject* object = asObject(array);
         return object->get(m_exec, m_exec->propertyNames().length).toUInt32(m_exec);
     }

     bool canDoFastRead(JSArray* array, unsigned index)
     {
         return isJSArray(&m_exec->globalData(), array) && array->canGetIndex(index);
     }

     JSValue getIndex(JSArray* array, unsigned index)
     {
         return array->getIndex(index);
     }

     JSValue getSparseIndex(JSObject* object, unsigned propertyName, bool& hasIndex)
     {
         PropertySlot slot(object);
         if (object->getOwnPropertySlot(m_exec, propertyName, slot)) {
             hasIndex = true;
             return slot.getValue(m_exec, propertyName);
         }
         hasIndex = false;
         return jsNull();
     }

     JSValue getProperty(JSObject* object, const Identifier& propertyName, unsigned)
     {
         PropertySlot slot(object);
         if (object->getOwnPropertySlot(m_exec, propertyName, slot))
             return slot.getValue(m_exec, propertyName);
         return jsNull();
     }

     SerializedScriptValueData convertIfTerminal(JSValue value)
     {
         if (!value.isCell())
             return SerializedScriptValueData(value);

         if (value.isString())
             return SerializedScriptValueData(asString(value)->value());

         if (value.isNumber())
             return SerializedScriptValueData(SerializedScriptValueData::NumberType, value.uncheckedGetNumber());

         if (value.isObject() && asObject(value)->inherits(&DateInstance::info))
             return SerializedScriptValueData(SerializedScriptValueData::DateType, asDateInstance(value)->internalNumber());

         if (isArray(value))
             return SerializedScriptValueData();

         CallData unusedData;
         if (value.isObject() && value.getCallData(unusedData) == CallTypeNone)
             return SerializedScriptValueData();

         // Any other types are expected to serialize as null.
         return SerializedScriptValueData(jsNull());
     }

     void getPropertyNames(JSObject* object, Vector<PropertyNameArray, 16>& propertyStack)
     {
         propertyStack.append(PropertyNameArray(m_exec));
         object->getOwnPropertyNames(m_exec, propertyStack.last());
     }

     void putProperty(RefPtr<SerializedArray> array, unsigned propertyName, const SerializedScriptValueData& value)
     {
         array->setIndex(propertyName, value);
     }

     void putProperty(RefPtr<SerializedObject> object, const Identifier& propertyName, const SerializedScriptValueData& value)
     {
         object->set(propertyName, value);
     }

     bool startArray(JSArray* inArray, RefPtr<SerializedArray>)
     {
         // Cycle detection
         if (!m_cycleDetector.add(inArray).second) {
             m_exec->setException(createTypeError(m_exec, "Cannot post cyclic structures."));
             return false;
         }
         m_gcBuffer.append(inArray);
         return true;
     }

     void endArray(JSArray* inArray, RefPtr<SerializedArray>)
     {
         m_cycleDetector.remove(inArray);
         m_gcBuffer.removeLast();
     }

     bool startObject(JSObject* inObject, RefPtr<SerializedObject>)
     {
         // Cycle detection
         if (!m_cycleDetector.add(inObject).second) {
             m_exec->setException(createTypeError(m_exec, "Cannot post cyclic structures."));
             return false;
         }
         m_gcBuffer.append(inObject);
         return true;
     }

     void endObject(JSObject* inObject, RefPtr<SerializedObject>)
     {
         m_cycleDetector.remove(inObject);
         m_gcBuffer.removeLast();
     }

 private:
     HashSet<JSObject*> m_cycleDetector;
 };

 SerializedScriptValueData SerializedScriptValueData::serialize(ExecState* exec, JSValue inValue)
 {
     SerializingTreeWalker context(exec);
     return walk<SerializingTreeWalker>(context, inValue);
 }


 struct DeserializingTreeWalker : public BaseWalker {
     typedef SerializedScriptValueData InputType;
     typedef RefPtr<SerializedArray> InputArray;
     typedef RefPtr<SerializedObject> InputObject;
     typedef JSValue OutputType;
     typedef JSArray* OutputArray;
     typedef JSObject* OutputObject;
     typedef SerializedObject::PropertyNameList PropertyList;

     DeserializingTreeWalker(ExecState* exec, bool mustCopy)
         : BaseWalker(exec)
         , m_mustCopy(mustCopy)
     {
     }

     OutputType null() { return jsNull(); }

     bool isArray(const SerializedScriptValueData& value)
     {
         return value.type() == SerializedScriptValueData::ArrayType;
     }

     bool isObject(const SerializedScriptValueData& value)
     {
         return value.type() == SerializedScriptValueData::ObjectType;
     }

     SerializedArray* asInputArray(const SerializedScriptValueData& value)
     {
         return value.asArray();
     }

     SerializedObject* asInputObject(const SerializedScriptValueData& value)
     {
         return value.asObject();
     }

     JSArray* createOutputArray(unsigned length)
     {
         JSArray* array = constructEmptyArray(m_exec);
         array->setLength(length);
         return array;
     }

     JSObject* createOutputObject()
     {
         return constructEmptyObject(m_exec);
     }

     uint32_t length(RefPtr<SerializedArray> array)
     {
         return array->length();
     }

     bool canDoFastRead(RefPtr<SerializedArray> array, unsigned index)
     {
         return array->canDoFastRead(index);
     }

     SerializedScriptValueData getIndex(RefPtr<SerializedArray> array, unsigned index)
     {
         return array->getIndex(index);
     }

     SerializedScriptValueData getSparseIndex(RefPtr<SerializedArray> array, unsigned propertyName, bool& hasIndex)
     {
         return array->getSparseIndex(propertyName, hasIndex);
     }

     SerializedScriptValueData getProperty(RefPtr<SerializedObject> object, const RefPtr<StringImpl>& propertyName, unsigned propertyIndex)
     {
         ASSERT(object->names()[propertyIndex] == propertyName);
         UNUSED_PARAM(propertyName);
         return object->values()[propertyIndex];
     }

     JSValue convertIfTerminal(SerializedScriptValueData& value)
     {
         switch (value.type()) {
             case SerializedScriptValueData::ArrayType:
             case SerializedScriptValueData::ObjectType:
                 return JSValue();
             case SerializedScriptValueData::StringType:
                 return jsString(m_exec, value.asString().crossThreadString());
             case SerializedScriptValueData::ImmediateType:
                 return value.asImmediate();
             case SerializedScriptValueData::NumberType:
                 return jsNumber(m_exec, value.asDouble());
             case SerializedScriptValueData::DateType:
                 return new (m_exec) DateInstance(m_exec, value.asDouble());
             default:
                 ASSERT_NOT_REACHED();
                 return JSValue();
         }
     }

     void getPropertyNames(RefPtr<SerializedObject> object, Vector<SerializedObject::PropertyNameList, 16>& properties)
     {
         properties.append(object->names());
     }

     void putProperty(JSArray* array, unsigned propertyName, JSValue value)
     {
         array->put(m_exec, propertyName, value);
     }

     void putProperty(JSObject* object, const RefPtr<StringImpl> propertyName, JSValue value)
     {
         object->putDirect(Identifier(m_exec, String(propertyName)), value);
     }

     bool startArray(RefPtr<SerializedArray>, JSArray* outArray)
     {
         m_gcBuffer.append(outArray);
         return true;
     }
     void endArray(RefPtr<SerializedArray>, JSArray*)
     {
         m_gcBuffer.removeLast();
     }
     bool startObject(RefPtr<SerializedObject>, JSObject* outObject)
     {
         m_gcBuffer.append(outObject);
         return true;
     }
     void endObject(RefPtr<SerializedObject>, JSObject*)
     {
         m_gcBuffer.removeLast();
     }

 private:
     bool m_mustCopy;
 };

 JSValue SerializedScriptValueData::deserialize(ExecState* exec, bool mustCopy) const
 {
     DeserializingTreeWalker context(exec, mustCopy);
     return walk<DeserializingTreeWalker>(context, *this);
 }

 struct TeardownTreeWalker {
     typedef SerializedScriptValueData InputType;
     typedef RefPtr<SerializedArray> InputArray;
     typedef RefPtr<SerializedObject> InputObject;
     typedef bool OutputType;
     typedef bool OutputArray;
     typedef bool OutputObject;
     typedef SerializedObject::PropertyNameList PropertyList;

     bool shouldTerminate()
     {
         return false;
     }

     unsigned ticksUntilNextCheck()
     {
         return 0xFFFFFFFF;
     }

     bool didTimeOut()
     {
         return false;
     }

     void throwStackOverflow()
     {
     }

     void throwInterruptedException()
     {
     }

     bool null() { return false; }

     bool isArray(const SerializedScriptValueData& value)
     {
         return value.type() == SerializedScriptValueData::ArrayType;
     }

     bool isObject(const SerializedScriptValueData& value)
     {
         return value.type() == SerializedScriptValueData::ObjectType;
     }

     SerializedArray* asInputArray(const SerializedScriptValueData& value)
     {
         return value.asArray();
     }

     SerializedObject* asInputObject(const SerializedScriptValueData& value)
     {
         return value.asObject();
     }

     bool createOutputArray(unsigned)
     {
         return false;
     }

     bool createOutputObject()
     {
         return false;
     }

     uint32_t length(RefPtr<SerializedArray> array)
     {
         return array->length();
     }

     bool canDoFastRead(RefPtr<SerializedArray> array, unsigned index)
     {
         return array->canDoFastRead(index);
     }

     SerializedScriptValueData getIndex(RefPtr<SerializedArray> array, unsigned index)
     {
         return array->getIndex(index);
     }

     SerializedScriptValueData getSparseIndex(RefPtr<SerializedArray> array, unsigned propertyName, bool& hasIndex)
     {
         return array->getSparseIndex(propertyName, hasIndex);
     }

     SerializedScriptValueData getProperty(RefPtr<SerializedObject> object, const RefPtr<StringImpl>& propertyName, unsigned propertyIndex)
     {
         ASSERT(object->names()[propertyIndex] == propertyName);
         UNUSED_PARAM(propertyName);
         return object->values()[propertyIndex];
     }

     bool convertIfTerminal(SerializedScriptValueData& value)
     {
         switch (value.type()) {
             case SerializedScriptValueData::ArrayType:
             case SerializedScriptValueData::ObjectType:
                 return false;
             case SerializedScriptValueData::StringType:
             case SerializedScriptValueData::ImmediateType:
             case SerializedScriptValueData::NumberType:
                 return true;
             default:
                 ASSERT_NOT_REACHED();
                 return JSValue();
         }
     }

     void getPropertyNames(RefPtr<SerializedObject> object, Vector<SerializedObject::PropertyNameList, 16>& properties)
     {
         properties.append(object->names());
     }

     void putProperty(bool, unsigned, bool)
     {
     }

     void putProperty(bool, const RefPtr<StringImpl>&, bool)
     {
     }

     bool startArray(RefPtr<SerializedArray>, bool)
     {
         return true;
     }
     void endArray(RefPtr<SerializedArray> array, bool)
     {
         array->clear();
     }
     bool startObject(RefPtr<SerializedObject>, bool)
     {
         return true;
     }
     void endObject(RefPtr<SerializedObject> object, bool)
     {
         object->clear();
     }
 };

 void SerializedScriptValueData::tearDownSerializedData()
 {
     if (m_sharedData && m_sharedData->refCount() > 1)
         return;
     TeardownTreeWalker context;
     walk<TeardownTreeWalker>(context, *this);
 }

 }
	/*
	* Copyright (C) 2009 Apple Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*
	*/

	#include "config.h"
	#include "SerializedScriptValue.h"

	#include <runtime/DateInstance.h>
	#include <runtime/ExceptionHelpers.h>
	#include <runtime/PropertyNameArray.h>
	#include <wtf/HashTraits.h>
	#include <wtf/Vector.h>

	using namespace JSC;

	namespace WebCore {

	class SerializedObject : public SharedSerializedData
	{
	public:
	typedef Vector<RefPtr<StringImpl> > PropertyNameList;
	typedef Vector<SerializedScriptValueData> ValueList;

	void set(const Identifier& propertyName, const SerializedScriptValueData& value)
	{
	ASSERT(m_names.size() == m_values.size());
	m_names.append(String(propertyName.ustring()).crossThreadString().impl());
	m_values.append(value);
	}

	PropertyNameList& names() { return m_names; }

	ValueList& values() { return m_values; }

	static PassRefPtr<SerializedObject> create()
	{
	return adoptRef(new SerializedObject);
	}

	void clear()
	{
	m_names.clear();
	m_values.clear();
	}

	private:
	SerializedObject() { }
	PropertyNameList m_names;
	ValueList m_values;
	};

	class SerializedArray : public SharedSerializedData
	{
	typedef HashMap<unsigned, SerializedScriptValueData, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned> > SparseMap;
	public:
	void setIndex(unsigned index, const SerializedScriptValueData& value)
	{
	ASSERT(index < m_length);
	if (index == m_compactStorage.size())
	m_compactStorage.append(value);
	else
	m_sparseStorage.set(index, value);
	}

	bool canDoFastRead(unsigned index) const
	{
	ASSERT(index < m_length);
	return index < m_compactStorage.size();
	}

	const SerializedScriptValueData& getIndex(unsigned index)
	{
	ASSERT(index < m_compactStorage.size());
	return m_compactStorage[index];
	}

	SerializedScriptValueData getSparseIndex(unsigned index, bool& hasIndex)
	{
	ASSERT(index >= m_compactStorage.size());
	ASSERT(index < m_length);
	SparseMap::iterator iter = m_sparseStorage.find(index);
	if (iter == m_sparseStorage.end()) {
	hasIndex = false;
	return SerializedScriptValueData();
	}
	hasIndex = true;
	return iter->second;
	}

	unsigned length() const
	{
	return m_length;
	}

	static PassRefPtr<SerializedArray> create(unsigned length)
	{
	return adoptRef(new SerializedArray(length));
	}

	void clear()
	{
	m_compactStorage.clear();
	m_sparseStorage.clear();
	m_length = 0;
	}
	private:
	SerializedArray(unsigned length)
	: m_length(length)
	{
	}

	Vector<SerializedScriptValueData> m_compactStorage;
	SparseMap m_sparseStorage;
	unsigned m_length;
	};

	SerializedScriptValueData::SerializedScriptValueData(RefPtr<SerializedObject> data)
	: m_type(ObjectType)
	, m_sharedData(data)
	{
	}

	SerializedScriptValueData::SerializedScriptValueData(RefPtr<SerializedArray> data)
	: m_type(ArrayType)
	, m_sharedData(data)
	{
	}

	SerializedArray* SharedSerializedData::asArray()
	{
	return static_cast<SerializedArray*>(this);
	}

	SerializedObject* SharedSerializedData::asObject()
	{
	return static_cast<SerializedObject*>(this);
	}

	static const unsigned maximumFilterRecursion = 40000;
	enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember,
	ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
	template <typename TreeWalker> typename TreeWalker::OutputType walk(TreeWalker& context, typename TreeWalker::InputType in)
	{
	typedef typename TreeWalker::InputObject InputObject;
	typedef typename TreeWalker::InputArray InputArray;
	typedef typename TreeWalker::OutputObject OutputObject;
	typedef typename TreeWalker::OutputArray OutputArray;
	typedef typename TreeWalker::InputType InputType;
	typedef typename TreeWalker::OutputType OutputType;
	typedef typename TreeWalker::PropertyList PropertyList;

	Vector<uint32_t, 16> indexStack;
	Vector<uint32_t, 16> lengthStack;
	Vector<PropertyList, 16> propertyStack;
	Vector<InputObject, 16> inputObjectStack;
	Vector<InputArray, 16> inputArrayStack;
	Vector<OutputObject, 16> outputObjectStack;
	Vector<OutputArray, 16> outputArrayStack;
	Vector<WalkerState, 16> stateStack;
	WalkerState state = StateUnknown;
	InputType inValue = in;
	OutputType outValue = context.null();

	unsigned tickCount = context.ticksUntilNextCheck();
	while (1) {
	switch (state) {
	arrayStartState:
	case ArrayStartState: {
	ASSERT(context.isArray(inValue));
	if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion) {
	context.throwStackOverflow();
	return context.null();
	}

	InputArray inArray = context.asInputArray(inValue);
	unsigned length = context.length(inArray);
	OutputArray outArray = context.createOutputArray(length);
	if (!context.startArray(inArray, outArray))
	return context.null();
	inputArrayStack.append(inArray);
	outputArrayStack.append(outArray);
	indexStack.append(0);
	lengthStack.append(length);
	// fallthrough
	}
	arrayStartVisitMember:
	case ArrayStartVisitMember: {
	if (!--tickCount) {
	if (context.didTimeOut()) {
	context.throwInterruptedException();
	return context.null();
	}
	tickCount = context.ticksUntilNextCheck();
	}

	InputArray array = inputArrayStack.last();
	uint32_t index = indexStack.last();
	if (index == lengthStack.last()) {
	InputArray inArray = inputArrayStack.last();
	OutputArray outArray = outputArrayStack.last();
	context.endArray(inArray, outArray);
	outValue = outArray;
	inputArrayStack.removeLast();
	outputArrayStack.removeLast();
	indexStack.removeLast();
	lengthStack.removeLast();
	break;
	}
	if (context.canDoFastRead(array, index))
	inValue = context.getIndex(array, index);
	else {
	bool hasIndex = false;
	inValue = context.getSparseIndex(array, index, hasIndex);
	if (!hasIndex) {
	indexStack.last()++;
	goto arrayStartVisitMember;
	}
	}

	if (OutputType transformed = context.convertIfTerminal(inValue))
	outValue = transformed;
	else {
	stateStack.append(ArrayEndVisitMember);
	goto stateUnknown;
	}
	// fallthrough
	}
	case ArrayEndVisitMember: {
	OutputArray outArray = outputArrayStack.last();
	context.putProperty(outArray, indexStack.last(), outValue);
	indexStack.last()++;
	goto arrayStartVisitMember;
	}
	objectStartState:
	case ObjectStartState: {
	ASSERT(context.isObject(inValue));
	if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion) {
	context.throwStackOverflow();
	return context.null();
	}
	InputObject inObject = context.asInputObject(inValue);
	OutputObject outObject = context.createOutputObject();
	if (!context.startObject(inObject, outObject))
	return context.null();
	inputObjectStack.append(inObject);
	outputObjectStack.append(outObject);
	indexStack.append(0);
	context.getPropertyNames(inObject, propertyStack);
	// fallthrough
	}
	objectStartVisitMember:
	case ObjectStartVisitMember: {
	if (!--tickCount) {
	if (context.didTimeOut()) {
	context.throwInterruptedException();
	return context.null();
	}
	tickCount = context.ticksUntilNextCheck();
	}

	InputObject object = inputObjectStack.last();
	uint32_t index = indexStack.last();
	PropertyList& properties = propertyStack.last();
	if (index == properties.size()) {
	InputObject inObject = inputObjectStack.last();
	OutputObject outObject = outputObjectStack.last();
	context.endObject(inObject, outObject);
	outValue = outObject;
	inputObjectStack.removeLast();
	outputObjectStack.removeLast();
	indexStack.removeLast();
	propertyStack.removeLast();
	break;
	}
	inValue = context.getProperty(object, properties[index], index);

	if (context.shouldTerminate())
	return context.null();

	if (OutputType transformed = context.convertIfTerminal(inValue))
	outValue = transformed;
	else {
	stateStack.append(ObjectEndVisitMember);
	goto stateUnknown;
	}
	// fallthrough
	}
	case ObjectEndVisitMember: {
	context.putProperty(outputObjectStack.last(), propertyStack.last()[indexStack.last()], outValue);
	if (context.shouldTerminate())
	return context.null();

	indexStack.last()++;
	goto objectStartVisitMember;
	}
	stateUnknown:
	case StateUnknown:
	if (OutputType transformed = context.convertIfTerminal(inValue)) {
	outValue = transformed;
	break;
	}
	if (context.isArray(inValue))
	goto arrayStartState;
	goto objectStartState;
	}
	if (stateStack.isEmpty())
	break;

	state = stateStack.last();
	stateStack.removeLast();

	if (!--tickCount) {
	if (context.didTimeOut()) {
	context.throwInterruptedException();
	return context.null();
	}
	tickCount = context.ticksUntilNextCheck();
	}
	}
	return outValue;
	}

	struct BaseWalker {
	BaseWalker(ExecState* exec)
	: m_exec(exec)
	, m_timeoutChecker(exec->globalData().timeoutChecker)
	{
	m_timeoutChecker.reset();
	}
	ExecState* m_exec;
	TimeoutChecker m_timeoutChecker;
	MarkedArgumentBuffer m_gcBuffer;

	bool shouldTerminate()
	{
	return m_exec->hadException();
	}

	unsigned ticksUntilNextCheck()
	{
	return m_timeoutChecker.ticksUntilNextCheck();
	}

	bool didTimeOut()
	{
	return m_timeoutChecker.didTimeOut(m_exec);
	}

	void throwStackOverflow()
	{
	m_exec->setException(createStackOverflowError(m_exec));
	}

	void throwInterruptedException()
	{
	m_exec->setException(createInterruptedExecutionException(&m_exec->globalData()));
	}
	};

	struct SerializingTreeWalker : public BaseWalker {
	typedef JSValue InputType;
	typedef JSArray* InputArray;
	typedef JSObject* InputObject;
	typedef SerializedScriptValueData OutputType;
	typedef RefPtr<SerializedArray> OutputArray;
	typedef RefPtr<SerializedObject> OutputObject;
	typedef PropertyNameArray PropertyList;

	SerializingTreeWalker(ExecState* exec)
	: BaseWalker(exec)
	{
	}

	OutputType null() { return SerializedScriptValueData(); }

	bool isArray(JSValue value)
	{
	if (!value.isObject())
	return false;
	JSObject* object = asObject(value);
	return isJSArray(&m_exec->globalData(), object) \|\| object->inherits(&JSArray::info);
	}

	bool isObject(JSValue value)
	{
	return value.isObject();
	}

	JSArray* asInputArray(JSValue value)
	{
	return asArray(value);
	}

	JSObject* asInputObject(JSValue value)
	{
	return asObject(value);
	}

	PassRefPtr<SerializedArray> createOutputArray(unsigned length)
	{
	return SerializedArray::create(length);
	}

	PassRefPtr<SerializedObject> createOutputObject()
	{
	return SerializedObject::create();
	}

	uint32_t length(JSValue array)
	{
	ASSERT(array.isObject());
	JSObject* object = asObject(array);
	return object->get(m_exec, m_exec->propertyNames().length).toUInt32(m_exec);
	}

	bool canDoFastRead(JSArray* array, unsigned index)
	{
	return isJSArray(&m_exec->globalData(), array) && array->canGetIndex(index);
	}

	JSValue getIndex(JSArray* array, unsigned index)
	{
	return array->getIndex(index);
	}

	JSValue getSparseIndex(JSObject* object, unsigned propertyName, bool& hasIndex)
	{
	PropertySlot slot(object);
	if (object->getOwnPropertySlot(m_exec, propertyName, slot)) {
	hasIndex = true;
	return slot.getValue(m_exec, propertyName);
	}
	hasIndex = false;
	return jsNull();
	}

	JSValue getProperty(JSObject* object, const Identifier& propertyName, unsigned)
	{
	PropertySlot slot(object);
	if (object->getOwnPropertySlot(m_exec, propertyName, slot))
	return slot.getValue(m_exec, propertyName);
	return jsNull();
	}

	SerializedScriptValueData convertIfTerminal(JSValue value)
	{
	if (!value.isCell())
	return SerializedScriptValueData(value);

	if (value.isString())
	return SerializedScriptValueData(asString(value)->value());

	if (value.isNumber())
	return SerializedScriptValueData(SerializedScriptValueData::NumberType, value.uncheckedGetNumber());

	if (value.isObject() && asObject(value)->inherits(&DateInstance::info))
	return SerializedScriptValueData(SerializedScriptValueData::DateType, asDateInstance(value)->internalNumber());

	if (isArray(value))
	return SerializedScriptValueData();

	CallData unusedData;
	if (value.isObject() && value.getCallData(unusedData) == CallTypeNone)
	return SerializedScriptValueData();

	// Any other types are expected to serialize as null.
	return SerializedScriptValueData(jsNull());
	}

	void getPropertyNames(JSObject* object, Vector<PropertyNameArray, 16>& propertyStack)
	{
	propertyStack.append(PropertyNameArray(m_exec));
	object->getOwnPropertyNames(m_exec, propertyStack.last());
	}

	void putProperty(RefPtr<SerializedArray> array, unsigned propertyName, const SerializedScriptValueData& value)
	{
	array->setIndex(propertyName, value);
	}

	void putProperty(RefPtr<SerializedObject> object, const Identifier& propertyName, const SerializedScriptValueData& value)
	{
	object->set(propertyName, value);
	}

	bool startArray(JSArray* inArray, RefPtr<SerializedArray>)
	{
	// Cycle detection
	if (!m_cycleDetector.add(inArray).second) {
	m_exec->setException(createTypeError(m_exec, "Cannot post cyclic structures."));
	return false;
	}
	m_gcBuffer.append(inArray);
	return true;
	}

	void endArray(JSArray* inArray, RefPtr<SerializedArray>)
	{
	m_cycleDetector.remove(inArray);
	m_gcBuffer.removeLast();
	}

	bool startObject(JSObject* inObject, RefPtr<SerializedObject>)
	{
	// Cycle detection
	if (!m_cycleDetector.add(inObject).second) {
	m_exec->setException(createTypeError(m_exec, "Cannot post cyclic structures."));
	return false;
	}
	m_gcBuffer.append(inObject);
	return true;
	}

	void endObject(JSObject* inObject, RefPtr<SerializedObject>)
	{
	m_cycleDetector.remove(inObject);
	m_gcBuffer.removeLast();
	}

	private:
	HashSet<JSObject*> m_cycleDetector;
	};

	SerializedScriptValueData SerializedScriptValueData::serialize(ExecState* exec, JSValue inValue)
	{
	SerializingTreeWalker context(exec);
	return walk<SerializingTreeWalker>(context, inValue);
	}


	struct DeserializingTreeWalker : public BaseWalker {
	typedef SerializedScriptValueData InputType;
	typedef RefPtr<SerializedArray> InputArray;
	typedef RefPtr<SerializedObject> InputObject;
	typedef JSValue OutputType;
	typedef JSArray* OutputArray;
	typedef JSObject* OutputObject;
	typedef SerializedObject::PropertyNameList PropertyList;

	DeserializingTreeWalker(ExecState* exec, bool mustCopy)
	: BaseWalker(exec)
	, m_mustCopy(mustCopy)
	{
	}

	OutputType null() { return jsNull(); }

	bool isArray(const SerializedScriptValueData& value)
	{
	return value.type() == SerializedScriptValueData::ArrayType;
	}

	bool isObject(const SerializedScriptValueData& value)
	{
	return value.type() == SerializedScriptValueData::ObjectType;
	}

	SerializedArray* asInputArray(const SerializedScriptValueData& value)
	{
	return value.asArray();
	}

	SerializedObject* asInputObject(const SerializedScriptValueData& value)
	{
	return value.asObject();
	}

	JSArray* createOutputArray(unsigned length)
	{
	JSArray* array = constructEmptyArray(m_exec);
	array->setLength(length);
	return array;
	}

	JSObject* createOutputObject()
	{
	return constructEmptyObject(m_exec);
	}

	uint32_t length(RefPtr<SerializedArray> array)
	{
	return array->length();
	}

	bool canDoFastRead(RefPtr<SerializedArray> array, unsigned index)
	{
	return array->canDoFastRead(index);
	}

	SerializedScriptValueData getIndex(RefPtr<SerializedArray> array, unsigned index)
	{
	return array->getIndex(index);
	}

	SerializedScriptValueData getSparseIndex(RefPtr<SerializedArray> array, unsigned propertyName, bool& hasIndex)
	{
	return array->getSparseIndex(propertyName, hasIndex);
	}

	SerializedScriptValueData getProperty(RefPtr<SerializedObject> object, const RefPtr<StringImpl>& propertyName, unsigned propertyIndex)
	{
	ASSERT(object->names()[propertyIndex] == propertyName);
	UNUSED_PARAM(propertyName);
	return object->values()[propertyIndex];
	}

	JSValue convertIfTerminal(SerializedScriptValueData& value)
	{
	switch (value.type()) {
	case SerializedScriptValueData::ArrayType:
	case SerializedScriptValueData::ObjectType:
	return JSValue();
	case SerializedScriptValueData::StringType:
	return jsString(m_exec, value.asString().crossThreadString());
	case SerializedScriptValueData::ImmediateType:
	return value.asImmediate();
	case SerializedScriptValueData::NumberType:
	return jsNumber(m_exec, value.asDouble());
	case SerializedScriptValueData::DateType:
	return new (m_exec) DateInstance(m_exec, value.asDouble());
	default:
	ASSERT_NOT_REACHED();
	return JSValue();
	}
	}

	void getPropertyNames(RefPtr<SerializedObject> object, Vector<SerializedObject::PropertyNameList, 16>& properties)
	{
	properties.append(object->names());
	}

	void putProperty(JSArray* array, unsigned propertyName, JSValue value)
	{
	array->put(m_exec, propertyName, value);
	}

	void putProperty(JSObject* object, const RefPtr<StringImpl> propertyName, JSValue value)
	{
	object->putDirect(Identifier(m_exec, String(propertyName)), value);
	}

	bool startArray(RefPtr<SerializedArray>, JSArray* outArray)
	{
	m_gcBuffer.append(outArray);
	return true;
	}
	void endArray(RefPtr<SerializedArray>, JSArray*)
	{
	m_gcBuffer.removeLast();
	}
	bool startObject(RefPtr<SerializedObject>, JSObject* outObject)
	{
	m_gcBuffer.append(outObject);
	return true;
	}
	void endObject(RefPtr<SerializedObject>, JSObject*)
	{
	m_gcBuffer.removeLast();
	}

	private:
	bool m_mustCopy;
	};

	JSValue SerializedScriptValueData::deserialize(ExecState* exec, bool mustCopy) const
	{
	DeserializingTreeWalker context(exec, mustCopy);
	return walk<DeserializingTreeWalker>(context, *this);
	}

	struct TeardownTreeWalker {
	typedef SerializedScriptValueData InputType;
	typedef RefPtr<SerializedArray> InputArray;
	typedef RefPtr<SerializedObject> InputObject;
	typedef bool OutputType;
	typedef bool OutputArray;
	typedef bool OutputObject;
	typedef SerializedObject::PropertyNameList PropertyList;

	bool shouldTerminate()
	{
	return false;
	}

	unsigned ticksUntilNextCheck()
	{
	return 0xFFFFFFFF;
	}

	bool didTimeOut()
	{
	return false;
	}

	void throwStackOverflow()
	{
	}

	void throwInterruptedException()
	{
	}

	bool null() { return false; }

	bool isArray(const SerializedScriptValueData& value)
	{
	return value.type() == SerializedScriptValueData::ArrayType;
	}

	bool isObject(const SerializedScriptValueData& value)
	{
	return value.type() == SerializedScriptValueData::ObjectType;
	}

	SerializedArray* asInputArray(const SerializedScriptValueData& value)
	{
	return value.asArray();
	}

	SerializedObject* asInputObject(const SerializedScriptValueData& value)
	{
	return value.asObject();
	}

	bool createOutputArray(unsigned)
	{
	return false;
	}

	bool createOutputObject()
	{
	return false;
	}

	uint32_t length(RefPtr<SerializedArray> array)
	{
	return array->length();
	}

	bool canDoFastRead(RefPtr<SerializedArray> array, unsigned index)
	{
	return array->canDoFastRead(index);
	}

	SerializedScriptValueData getIndex(RefPtr<SerializedArray> array, unsigned index)
	{
	return array->getIndex(index);
	}

	SerializedScriptValueData getSparseIndex(RefPtr<SerializedArray> array, unsigned propertyName, bool& hasIndex)
	{
	return array->getSparseIndex(propertyName, hasIndex);
	}

	SerializedScriptValueData getProperty(RefPtr<SerializedObject> object, const RefPtr<StringImpl>& propertyName, unsigned propertyIndex)
	{
	ASSERT(object->names()[propertyIndex] == propertyName);
	UNUSED_PARAM(propertyName);
	return object->values()[propertyIndex];
	}

	bool convertIfTerminal(SerializedScriptValueData& value)
	{
	switch (value.type()) {
	case SerializedScriptValueData::ArrayType:
	case SerializedScriptValueData::ObjectType:
	return false;
	case SerializedScriptValueData::StringType:
	case SerializedScriptValueData::ImmediateType:
	case SerializedScriptValueData::NumberType:
	return true;
	default:
	ASSERT_NOT_REACHED();
	return JSValue();
	}
	}

	void getPropertyNames(RefPtr<SerializedObject> object, Vector<SerializedObject::PropertyNameList, 16>& properties)
	{
	properties.append(object->names());
	}

	void putProperty(bool, unsigned, bool)
	{
	}

	void putProperty(bool, const RefPtr<StringImpl>&, bool)
	{
	}

	bool startArray(RefPtr<SerializedArray>, bool)
	{
	return true;
	}
	void endArray(RefPtr<SerializedArray> array, bool)
	{
	array->clear();
	}
	bool startObject(RefPtr<SerializedObject>, bool)
	{
	return true;
	}
	void endObject(RefPtr<SerializedObject> object, bool)
	{
	object->clear();
	}
	};

	void SerializedScriptValueData::tearDownSerializedData()
	{
	if (m_sharedData && m_sharedData->refCount() > 1)
	return;
	TeardownTreeWalker context;
	walk<TeardownTreeWalker>(context, *this);
	}

	}