WebCore/bindings/v8/SerializedScriptValue.cpp

/*
 * Copyright (C) 2010 Google 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:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * 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.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "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 THE COPYRIGHT
 * OWNER 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 "SharedBuffer.h"

#include <v8.h>
#include <wtf/Assertions.h>
#include <wtf/RefCounted.h>
#include <wtf/Vector.h>

// FIXME:
// - catch V8 exceptions
// - be ready to get empty handles
// - consider crashing in debug mode on deserialization errors

namespace WebCore {

namespace {

typedef UChar BufferValueType;

// Serialization format is a sequence of (tag, optional data)
// pairs. Tag always takes exactly one byte.
enum SerializationTag {
    InvalidTag = '!',
    PaddingTag = '\0',
    UndefinedTag = '_',
    NullTag = '0',
    TrueTag = 'T',
    FalseTag = 'F',
    StringTag = 'S',
    Int32Tag = 'I',
    NumberTag = 'N',
    ObjectTag = '{',
    ArrayTag = '[',
};

// Helpers to do verbose handle casts.

template <typename T, typename U>
static v8::Handle<T> handleCast(v8::Handle<U> handle) { return v8::Handle<T>::Cast(handle); }

template <typename T, typename U>
static v8::Local<T> handleCast(v8::Local<U> handle) { return v8::Local<T>::Cast(handle); }

static bool shouldCheckForCycles(int depth)
{
    ASSERT(depth >= 0);
    // Since we are not required to spot the cycle as soon as it
    // happens we can check for cycles only when the current depth
    // is a power of two.
    return !(depth & (depth - 1));
}

static const int maxDepth = 20000;

// VarInt encoding constants.
static const int varIntShift = 7;
static const int varIntMask = (1 << varIntShift) - 1;

// ZigZag encoding helps VarInt encoding stay small for negative
// numbers with small absolute values.
class ZigZag {
public:
    static uint32_t encode(uint32_t value)
    {
        if (value & (1U << 31))
            value = ((~value) << 1) + 1;
        else
            value <<= 1;
        return value;
    }

    static uint32_t decode(uint32_t value)
    {
        if (value & 1)
            value = ~(value >> 1);
        else
            value >>= 1;
        return value;
    }

private:
    ZigZag();
};

// Writer is responsible for serializing primitive types and storing
// information used to reconstruct composite types.
class Writer : Noncopyable {
public:
    Writer() : m_position(0)
    {
    }

    // Write functions for primitive types.

    void writeUndefined() { append(UndefinedTag); }

    void writeNull() { append(NullTag); }

    void writeTrue() { append(TrueTag); }

    void writeFalse() { append(FalseTag); }

    void writeString(const char* data, int length)
    {
        append(StringTag);
        doWriteUint32(static_cast<uint32_t>(length));
        append(data, length);
    }

    void writeInt32(int32_t value)
    {
        append(Int32Tag);
        doWriteUint32(ZigZag::encode(static_cast<uint32_t>(value)));
    }

    void writeNumber(double number)
    {
        append(NumberTag);
        append(reinterpret_cast<char*>(&number), sizeof(number));
    }

    // Records that a composite object can be constructed by using
    // |length| previously stored values.
    void endComposite(SerializationTag tag, int32_t length)
    {
        ASSERT(tag == ObjectTag || tag == ArrayTag);
        append(tag);
        doWriteUint32(static_cast<uint32_t>(length));
    }

    Vector<BufferValueType>& data()
    {
        fillHole();
        return m_buffer;
    }

private:
    void doWriteUint32(uint32_t value)
    {
        while (true) {
            char b = (value & varIntMask);
            value >>= varIntShift;
            if (!value) {
                append(b);
                break;
            }
            append(b | (1 << varIntShift));
        }
    }

    void append(SerializationTag tag)
    {
        append(static_cast<char>(tag));
    }

    void append(char b)
    {
        ensureSpace(1);
        *charAt(m_position++) = b;
    }

    void append(const char* data, int length)
    {
        ensureSpace(length);
        memcpy(charAt(m_position), data, length);
        m_position += length;
    }

    void ensureSpace(int extra)
    {
        COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
        m_buffer.grow((m_position + extra + 1) / 2); // "+ 1" to round up.
    }

    void fillHole()
    {
        COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
        // If the writer is at odd position in the buffer, then one of
        // the bytes in the last UChar is not initialized.
        if (m_position % 2)
            *charAt(m_position) = static_cast<char>(PaddingTag);
    }

    char* charAt(int position) { return reinterpret_cast<char*>(m_buffer.data()) + position; }

    Vector<BufferValueType> m_buffer;
    unsigned m_position;
};

class Serializer {
public:
    explicit Serializer(Writer& writer)
        : m_writer(writer)
        , m_state(0)
        , m_depth(0)
    {
    }

    bool serialize(v8::Handle<v8::Value> value)
    {
        v8::HandleScope scope;
        StackCleaner cleaner(&m_state);
        if (!doSerialize(value))
            return false;
        while (top()) {
            int length;
            while (!top()->isDone(&length)) {
                // Note that doSerialize() can change current top().
                if (!doSerialize(top()->advance()))
                    return false;
            }
            m_writer.endComposite(top()->tag(), length);
            pop();
        }
        return true;
    }

private:
    class StateBase : public Noncopyable {
    public:
        virtual ~StateBase() { }

        // Link to the next state to form a stack.
        StateBase* nextState() { return m_next; }
        void setNextState(StateBase* next) { m_next = next; }

        // Composite object we're processing in this state.
        v8::Handle<v8::Value> composite() { return m_composite; }

        // Serialization tag for the current composite.
        virtual SerializationTag tag() const = 0;

        // Returns whether iteration over subobjects of the current
        // composite object is done. If yes, |*length| is set to the
        // number of subobjects.
        virtual bool isDone(int* length) = 0;

        // Advances to the next subobject.
        // Requires: !this->isDone().
        virtual v8::Local<v8::Value> advance() = 0;

    protected:
        StateBase(v8::Handle<v8::Value> composite)
            : m_next(0)
            , m_composite(composite)
        {
        }

    private:
        StateBase* m_next;
        v8::Handle<v8::Value> m_composite;
    };

    template <typename T, SerializationTag compositeTag>
    class State : public StateBase {
    public:
        v8::Handle<T> composite() { return handleCast<T>(StateBase::composite()); }

        virtual SerializationTag tag() const { return compositeTag; }

    protected:
        explicit State(v8::Handle<T> composite) : StateBase(composite)
        {
        }
    };

    // Helper to clean up the state stack in case of errors.
    class StackCleaner : Noncopyable {
    public:
        explicit StackCleaner(StateBase** stack) : m_stack(stack)
        {
        }

        ~StackCleaner()
        {
            StateBase* state = *m_stack;
            while (state) {
                StateBase* tmp = state->nextState();
                delete state;
                state = tmp;
            }
            *m_stack = 0;
        }

    private:
        StateBase** m_stack;
    };

    class ArrayState : public State<v8::Array, ArrayTag> {
    public:
        ArrayState(v8::Handle<v8::Array> array)
            : State<v8::Array, ArrayTag>(array)
            , m_index(0)
        {
        }

        virtual bool isDone(int* length)
        {
            *length = composite()->Length();
            return static_cast<int>(m_index) >= *length;
        }

        virtual v8::Local<v8::Value> advance()
        {
            ASSERT(m_index < composite()->Length());
            v8::HandleScope scope;
            return scope.Close(composite()->Get(v8::Integer::New(m_index++)));
        }

    private:
        unsigned m_index;
    };

    class ObjectState : public State<v8::Object, ObjectTag> {
    public:
        ObjectState(v8::Handle<v8::Object> object)
            : State<v8::Object, ObjectTag>(object)
            , m_propertyNames(object->GetPropertyNames())
            , m_index(-1)
            , m_length(0)
        {
            nextProperty();
        }

        virtual bool isDone(int* length)
        {
            *length = m_length;
            return m_index >= 2 * m_propertyNames->Length();
        }

        virtual v8::Local<v8::Value> advance()
        {
            ASSERT(m_index < 2 * m_propertyNames->Length());
            if (!(m_index % 2)) {
                ++m_index;
                return m_propertyName;
            }
            v8::Local<v8::Value> result = composite()->Get(m_propertyName);
            nextProperty();
            return result;
        }

    private:
        void nextProperty()
        {
            v8::HandleScope scope;
            ++m_index;
            ASSERT(!(m_index % 2));
            for (; m_index < 2 * m_propertyNames->Length(); m_index += 2) {
                v8::Local<v8::Value> propertyName = m_propertyNames->Get(v8::Integer::New(m_index / 2));
                if ((propertyName->IsString() && composite()->HasRealNamedProperty(handleCast<v8::String>(propertyName)))
                    || (propertyName->IsInt32() && composite()->HasRealIndexedProperty(propertyName->Uint32Value()))) {
                    m_propertyName = scope.Close(propertyName);
                    m_length += 2;
                    return;
                }
            }
        }

        v8::Local<v8::Array> m_propertyNames;
        v8::Local<v8::Value> m_propertyName;
        unsigned m_index;
        unsigned m_length;
    };

    bool doSerialize(v8::Handle<v8::Value> value)
    {
        if (value->IsUndefined())
            m_writer.writeUndefined();
        else if (value->IsNull())
            m_writer.writeNull();
        else if (value->IsTrue())
            m_writer.writeTrue();
        else if (value->IsFalse())
            m_writer.writeFalse();
        else if (value->IsInt32())
            m_writer.writeInt32(value->Int32Value());
        else if (value->IsNumber())
            m_writer.writeNumber(handleCast<v8::Number>(value)->Value());
        else if (value->IsString()) {
            v8::String::Utf8Value stringValue(value);
            m_writer.writeString(*stringValue, stringValue.length());
        } else if (value->IsArray()) {
            if (!checkComposite(value))
                return false;
            push(new ArrayState(handleCast<v8::Array>(value)));
        } else if (value->IsObject()) {
            if (!checkComposite(value))
                return false;
            push(new ObjectState(handleCast<v8::Object>(value)));
            // FIXME:
            // - check not a wrapper
            // - support File, ImageData, etc.
        }
        return true;
    }

    void push(StateBase* state)
    {
        state->setNextState(m_state);
        m_state = state;
        ++m_depth;
    }

    StateBase* top() { return m_state; }

    void pop()
    {
        if (!m_state)
            return;
        StateBase* top = m_state;
        m_state = top->nextState();
        delete top;
        --m_depth;
    }

    bool checkComposite(v8::Handle<v8::Value> composite)
    {
        if (m_depth > maxDepth)
            return false;
        if (!shouldCheckForCycles(m_depth))
            return true;
        for (StateBase* state = top(); state; state = state->nextState()) {
            if (state->composite() == composite)
                return false;
        }
        return true;
    }

    Writer& m_writer;
    StateBase* m_state;
    int m_depth;
};

// Reader is responsible for deserializing primitive types and
// restoring information about saved objects of composite types.
class Reader {
public:
    Reader(const char* buffer, int length)
        : m_buffer(buffer)
        , m_length(length)
        , m_position(0)
    {
        ASSERT(length >= 0);
    }

    bool isEof() const { return m_position >= m_length; }

    bool read(SerializationTag* tag, v8::Handle<v8::Value>* value, int* length)
    {
        uint32_t rawLength;
        if (!readTag(tag))
            return false;
        switch (*tag) {
        case InvalidTag:
            return false;
        case PaddingTag:
            break;
        case UndefinedTag:
            *value = v8::Undefined();
            break;
        case NullTag:
            *value = v8::Null();
            break;
        case TrueTag:
            *value = v8::True();
            break;
        case FalseTag:
            *value = v8::False();
            break;
        case StringTag:
            if (!readString(value))
                return false;
            break;
        case Int32Tag:
            if (!readInt32(value))
                return false;
            break;
        case NumberTag:
            if (!readNumber(value))
                return false;
            break;
        case ObjectTag:
        case ArrayTag:
            if (!doReadUint32(&rawLength))
                return false;
            *length = rawLength;
            break;
        }
        return true;
    }

private:
    bool readTag(SerializationTag* tag)
    {
        if (m_position >= m_length)
            return false;
        *tag = static_cast<SerializationTag>(m_buffer[m_position++]);
        return true;
    }

    bool readString(v8::Handle<v8::Value>* value)
    {
        uint32_t length;
        if (!doReadUint32(&length))
            return false;
        if (m_position + length > m_length)
            return false;
        *value = v8::String::New(m_buffer + m_position, length);
        m_position += length;
        return true;
    }

    bool readInt32(v8::Handle<v8::Value>* value)
    {
        uint32_t rawValue;
        if (!doReadUint32(&rawValue))
            return false;
        *value = v8::Integer::New(static_cast<int32_t>(ZigZag::decode(rawValue)));
        return true;
    }

    bool readNumber(v8::Handle<v8::Value>* value)
    {
        if (m_position + sizeof(double) > m_length)
            return false;
        double number;
        char* numberAsByteArray = reinterpret_cast<char*>(&number);
        for (unsigned i = 0; i < sizeof(double); ++i)
            numberAsByteArray[i] = m_buffer[m_position++];
        *value = v8::Number::New(number);
        return true;
    }

    bool doReadUint32(uint32_t* value)
    {
        *value = 0;
        char currentByte;
        int shift = 0;
        do {
            if (m_position >= m_length)
                return false;
            currentByte = m_buffer[m_position++];
            *value |= ((currentByte & varIntMask) << shift);
            shift += varIntShift;
        } while (currentByte & (1 << varIntShift));
        return true;
    }

    const char* m_buffer;
    const unsigned m_length;
    unsigned m_position;
};

class Deserializer {
public:
    explicit Deserializer(Reader& reader) : m_reader(reader)
    {
    }

    v8::Local<v8::Value> deserialize()
    {
        v8::HandleScope scope;
        while (!m_reader.isEof()) {
            if (!doDeserialize())
                return v8::Local<v8::Value>();
        }
        if (stackDepth() != 1)
            return v8::Local<v8::Value>();
        return scope.Close(element(0));
    }

private:
    bool doDeserialize()
    {
        SerializationTag tag;
        v8::Local<v8::Value> value;
        int length = 0;
        if (!m_reader.read(&tag, &value, &length))
            return false;
        if (!value.IsEmpty()) {
            push(value);
        } else if (tag == ObjectTag) {
            if (length > stackDepth())
                return false;
            v8::Local<v8::Object> object = v8::Object::New();
            for (int i = stackDepth() - length; i < stackDepth(); i += 2) {
                v8::Local<v8::Value> propertyName = element(i);
                v8::Local<v8::Value> propertyValue = element(i + 1);
                object->Set(propertyName, propertyValue);
            }
            pop(length);
            push(object);
        } else if (tag == ArrayTag) {
            if (length > stackDepth())
                return false;
            v8::Local<v8::Array> array = v8::Array::New(length);
            const int depth = stackDepth() - length;
            {
                v8::HandleScope scope;
                for (int i = 0; i < length; ++i)
                    array->Set(v8::Integer::New(i), element(depth + i));
            }
            pop(length);
            push(array);
        } else if (tag != PaddingTag)
            return false;
        return true;
    }

    void push(v8::Local<v8::Value> value) { m_stack.append(value); }

    void pop(unsigned length)
    {
        ASSERT(length <= m_stack.size());
        m_stack.shrink(m_stack.size() - length);
    }

    int stackDepth() const { return m_stack.size(); }

    v8::Local<v8::Value> element(unsigned index)
    {
        ASSERT(index < m_stack.size());
        return m_stack[index];
    }

    Reader& m_reader;
    Vector<v8::Local<v8::Value> > m_stack;
};

} // namespace

SerializedScriptValue::SerializedScriptValue(v8::Handle<v8::Value> value)
{
    Writer writer;
    Serializer serializer(writer);
    if (!serializer.serialize(value)) {
        // FIXME: throw exception
        return;
    }
    m_data = StringImpl::adopt(writer.data());
}

SerializedScriptValue::SerializedScriptValue(String data, StringDataMode mode)
{
    if (mode == WireData)
        m_data = data;
    else {
        ASSERT(mode == StringValue);
        RefPtr<SharedBuffer> buffer = utf8Buffer(data);
        Writer writer;
        writer.writeString(buffer->data(), buffer->size());
        m_data = StringImpl::adopt(writer.data());
    }
}

v8::Local<v8::Value> SerializedScriptValue::deserialize()
{
    if (!m_data.impl())
        return v8::Local<v8::Value>();
    COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
    Reader reader(reinterpret_cast<const char*>(m_data.impl()->characters()), 2 * m_data.length());
    Deserializer deserializer(reader);
    return deserializer.deserialize();
}

} // namespace WebCore