1/*
2 * Copyright (C) 2010 Google 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 are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "config.h"
32#include "SerializedScriptValue.h"
33
34#include "SharedBuffer.h"
35
36#include <v8.h>
37#include <wtf/Assertions.h>
38#include <wtf/RefCounted.h>
39#include <wtf/Vector.h>
40
41// FIXME:
42// - catch V8 exceptions
43// - be ready to get empty handles
44// - consider crashing in debug mode on deserialization errors
45
46namespace WebCore {
47
48namespace {
49
50typedef UChar BufferValueType;
51
52// Serialization format is a sequence of (tag, optional data)
53// pairs. Tag always takes exactly one byte.
54enum SerializationTag {
55    InvalidTag = '!',
56    PaddingTag = '\0',
57    UndefinedTag = '_',
58    NullTag = '0',
59    TrueTag = 'T',
60    FalseTag = 'F',
61    StringTag = 'S',
62    Int32Tag = 'I',
63    NumberTag = 'N',
64    ObjectTag = '{',
65    ArrayTag = '[',
66};
67
68// Helpers to do verbose handle casts.
69
70template <typename T, typename U>
71static v8::Handle<T> handleCast(v8::Handle<U> handle) { return v8::Handle<T>::Cast(handle); }
72
73template <typename T, typename U>
74static v8::Local<T> handleCast(v8::Local<U> handle) { return v8::Local<T>::Cast(handle); }
75
76static bool shouldCheckForCycles(int depth)
77{
78    ASSERT(depth >= 0);
79    // Since we are not required to spot the cycle as soon as it
80    // happens we can check for cycles only when the current depth
81    // is a power of two.
82    return !(depth & (depth - 1));
83}
84
85static const int maxDepth = 20000;
86
87// VarInt encoding constants.
88static const int varIntShift = 7;
89static const int varIntMask = (1 << varIntShift) - 1;
90
91// ZigZag encoding helps VarInt encoding stay small for negative
92// numbers with small absolute values.
93class ZigZag {
94public:
95    static uint32_t encode(uint32_t value)
96    {
97        if (value & (1U << 31))
98            value = ((~value) << 1) + 1;
99        else
100            value <<= 1;
101        return value;
102    }
103
104    static uint32_t decode(uint32_t value)
105    {
106        if (value & 1)
107            value = ~(value >> 1);
108        else
109            value >>= 1;
110        return value;
111    }
112
113private:
114    ZigZag();
115};
116
117// Writer is responsible for serializing primitive types and storing
118// information used to reconstruct composite types.
119class Writer : Noncopyable {
120public:
121    Writer() : m_position(0)
122    {
123    }
124
125    // Write functions for primitive types.
126
127    void writeUndefined() { append(UndefinedTag); }
128
129    void writeNull() { append(NullTag); }
130
131    void writeTrue() { append(TrueTag); }
132
133    void writeFalse() { append(FalseTag); }
134
135    void writeString(const char* data, int length)
136    {
137        append(StringTag);
138        doWriteUint32(static_cast<uint32_t>(length));
139        append(data, length);
140    }
141
142    void writeInt32(int32_t value)
143    {
144        append(Int32Tag);
145        doWriteUint32(ZigZag::encode(static_cast<uint32_t>(value)));
146    }
147
148    void writeNumber(double number)
149    {
150        append(NumberTag);
151        append(reinterpret_cast<char*>(&number), sizeof(number));
152    }
153
154    // Records that a composite object can be constructed by using
155    // |length| previously stored values.
156    void endComposite(SerializationTag tag, int32_t length)
157    {
158        ASSERT(tag == ObjectTag || tag == ArrayTag);
159        append(tag);
160        doWriteUint32(static_cast<uint32_t>(length));
161    }
162
163    Vector<BufferValueType>& data()
164    {
165        fillHole();
166        return m_buffer;
167    }
168
169private:
170    void doWriteUint32(uint32_t value)
171    {
172        while (true) {
173            char b = (value & varIntMask);
174            value >>= varIntShift;
175            if (!value) {
176                append(b);
177                break;
178            }
179            append(b | (1 << varIntShift));
180        }
181    }
182
183    void append(SerializationTag tag)
184    {
185        append(static_cast<char>(tag));
186    }
187
188    void append(char b)
189    {
190        ensureSpace(1);
191        *charAt(m_position++) = b;
192    }
193
194    void append(const char* data, int length)
195    {
196        ensureSpace(length);
197        memcpy(charAt(m_position), data, length);
198        m_position += length;
199    }
200
201    void ensureSpace(int extra)
202    {
203        COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
204        m_buffer.grow((m_position + extra + 1) / 2); // "+ 1" to round up.
205    }
206
207    void fillHole()
208    {
209        COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
210        // If the writer is at odd position in the buffer, then one of
211        // the bytes in the last UChar is not initialized.
212        if (m_position % 2)
213            *charAt(m_position) = static_cast<char>(PaddingTag);
214    }
215
216    char* charAt(int position) { return reinterpret_cast<char*>(m_buffer.data()) + position; }
217
218    Vector<BufferValueType> m_buffer;
219    unsigned m_position;
220};
221
222class Serializer {
223public:
224    explicit Serializer(Writer& writer)
225        : m_writer(writer)
226        , m_state(0)
227        , m_depth(0)
228    {
229    }
230
231    bool serialize(v8::Handle<v8::Value> value)
232    {
233        v8::HandleScope scope;
234        StackCleaner cleaner(&m_state);
235        if (!doSerialize(value))
236            return false;
237        while (top()) {
238            int length;
239            while (!top()->isDone(&length)) {
240                // Note that doSerialize() can change current top().
241                if (!doSerialize(top()->advance()))
242                    return false;
243            }
244            m_writer.endComposite(top()->tag(), length);
245            pop();
246        }
247        return true;
248    }
249
250private:
251    class StateBase : public Noncopyable {
252    public:
253        virtual ~StateBase() { }
254
255        // Link to the next state to form a stack.
256        StateBase* nextState() { return m_next; }
257        void setNextState(StateBase* next) { m_next = next; }
258
259        // Composite object we're processing in this state.
260        v8::Handle<v8::Value> composite() { return m_composite; }
261
262        // Serialization tag for the current composite.
263        virtual SerializationTag tag() const = 0;
264
265        // Returns whether iteration over subobjects of the current
266        // composite object is done. If yes, |*length| is set to the
267        // number of subobjects.
268        virtual bool isDone(int* length) = 0;
269
270        // Advances to the next subobject.
271        // Requires: !this->isDone().
272        virtual v8::Local<v8::Value> advance() = 0;
273
274    protected:
275        StateBase(v8::Handle<v8::Value> composite)
276            : m_next(0)
277            , m_composite(composite)
278        {
279        }
280
281    private:
282        StateBase* m_next;
283        v8::Handle<v8::Value> m_composite;
284    };
285
286    template <typename T, SerializationTag compositeTag>
287    class State : public StateBase {
288    public:
289        v8::Handle<T> composite() { return handleCast<T>(StateBase::composite()); }
290
291        virtual SerializationTag tag() const { return compositeTag; }
292
293    protected:
294        explicit State(v8::Handle<T> composite) : StateBase(composite)
295        {
296        }
297    };
298
299    // Helper to clean up the state stack in case of errors.
300    class StackCleaner : Noncopyable {
301    public:
302        explicit StackCleaner(StateBase** stack) : m_stack(stack)
303        {
304        }
305
306        ~StackCleaner()
307        {
308            StateBase* state = *m_stack;
309            while (state) {
310                StateBase* tmp = state->nextState();
311                delete state;
312                state = tmp;
313            }
314            *m_stack = 0;
315        }
316
317    private:
318        StateBase** m_stack;
319    };
320
321    class ArrayState : public State<v8::Array, ArrayTag> {
322    public:
323        ArrayState(v8::Handle<v8::Array> array)
324            : State<v8::Array, ArrayTag>(array)
325            , m_index(0)
326        {
327        }
328
329        virtual bool isDone(int* length)
330        {
331            *length = composite()->Length();
332            return static_cast<int>(m_index) >= *length;
333        }
334
335        virtual v8::Local<v8::Value> advance()
336        {
337            ASSERT(m_index < composite()->Length());
338            v8::HandleScope scope;
339            return scope.Close(composite()->Get(v8::Integer::New(m_index++)));
340        }
341
342    private:
343        unsigned m_index;
344    };
345
346    class ObjectState : public State<v8::Object, ObjectTag> {
347    public:
348        ObjectState(v8::Handle<v8::Object> object)
349            : State<v8::Object, ObjectTag>(object)
350            , m_propertyNames(object->GetPropertyNames())
351            , m_index(-1)
352            , m_length(0)
353        {
354            nextProperty();
355        }
356
357        virtual bool isDone(int* length)
358        {
359            *length = m_length;
360            return m_index >= 2 * m_propertyNames->Length();
361        }
362
363        virtual v8::Local<v8::Value> advance()
364        {
365            ASSERT(m_index < 2 * m_propertyNames->Length());
366            if (!(m_index % 2)) {
367                ++m_index;
368                return m_propertyName;
369            }
370            v8::Local<v8::Value> result = composite()->Get(m_propertyName);
371            nextProperty();
372            return result;
373        }
374
375    private:
376        void nextProperty()
377        {
378            v8::HandleScope scope;
379            ++m_index;
380            ASSERT(!(m_index % 2));
381            for (; m_index < 2 * m_propertyNames->Length(); m_index += 2) {
382                v8::Local<v8::Value> propertyName = m_propertyNames->Get(v8::Integer::New(m_index / 2));
383                if ((propertyName->IsString() && composite()->HasRealNamedProperty(handleCast<v8::String>(propertyName)))
384                    || (propertyName->IsInt32() && composite()->HasRealIndexedProperty(propertyName->Uint32Value()))) {
385                    m_propertyName = scope.Close(propertyName);
386                    m_length += 2;
387                    return;
388                }
389            }
390        }
391
392        v8::Local<v8::Array> m_propertyNames;
393        v8::Local<v8::Value> m_propertyName;
394        unsigned m_index;
395        unsigned m_length;
396    };
397
398    bool doSerialize(v8::Handle<v8::Value> value)
399    {
400        if (value->IsUndefined())
401            m_writer.writeUndefined();
402        else if (value->IsNull())
403            m_writer.writeNull();
404        else if (value->IsTrue())
405            m_writer.writeTrue();
406        else if (value->IsFalse())
407            m_writer.writeFalse();
408        else if (value->IsInt32())
409            m_writer.writeInt32(value->Int32Value());
410        else if (value->IsNumber())
411            m_writer.writeNumber(handleCast<v8::Number>(value)->Value());
412        else if (value->IsString()) {
413            v8::String::Utf8Value stringValue(value);
414            m_writer.writeString(*stringValue, stringValue.length());
415        } else if (value->IsArray()) {
416            if (!checkComposite(value))
417                return false;
418            push(new ArrayState(handleCast<v8::Array>(value)));
419        } else if (value->IsObject()) {
420            if (!checkComposite(value))
421                return false;
422            push(new ObjectState(handleCast<v8::Object>(value)));
423            // FIXME:
424            // - check not a wrapper
425            // - support File, ImageData, etc.
426        }
427        return true;
428    }
429
430    void push(StateBase* state)
431    {
432        state->setNextState(m_state);
433        m_state = state;
434        ++m_depth;
435    }
436
437    StateBase* top() { return m_state; }
438
439    void pop()
440    {
441        if (!m_state)
442            return;
443        StateBase* top = m_state;
444        m_state = top->nextState();
445        delete top;
446        --m_depth;
447    }
448
449    bool checkComposite(v8::Handle<v8::Value> composite)
450    {
451        if (m_depth > maxDepth)
452            return false;
453        if (!shouldCheckForCycles(m_depth))
454            return true;
455        for (StateBase* state = top(); state; state = state->nextState()) {
456            if (state->composite() == composite)
457                return false;
458        }
459        return true;
460    }
461
462    Writer& m_writer;
463    StateBase* m_state;
464    int m_depth;
465};
466
467// Reader is responsible for deserializing primitive types and
468// restoring information about saved objects of composite types.
469class Reader {
470public:
471    Reader(const char* buffer, int length)
472        : m_buffer(buffer)
473        , m_length(length)
474        , m_position(0)
475    {
476        ASSERT(length >= 0);
477    }
478
479    bool isEof() const { return m_position >= m_length; }
480
481    bool read(SerializationTag* tag, v8::Handle<v8::Value>* value, int* length)
482    {
483        uint32_t rawLength;
484        if (!readTag(tag))
485            return false;
486        switch (*tag) {
487        case InvalidTag:
488            return false;
489        case PaddingTag:
490            break;
491        case UndefinedTag:
492            *value = v8::Undefined();
493            break;
494        case NullTag:
495            *value = v8::Null();
496            break;
497        case TrueTag:
498            *value = v8::True();
499            break;
500        case FalseTag:
501            *value = v8::False();
502            break;
503        case StringTag:
504            if (!readString(value))
505                return false;
506            break;
507        case Int32Tag:
508            if (!readInt32(value))
509                return false;
510            break;
511        case NumberTag:
512            if (!readNumber(value))
513                return false;
514            break;
515        case ObjectTag:
516        case ArrayTag:
517            if (!doReadUint32(&rawLength))
518                return false;
519            *length = rawLength;
520            break;
521        }
522        return true;
523    }
524
525private:
526    bool readTag(SerializationTag* tag)
527    {
528        if (m_position >= m_length)
529            return false;
530        *tag = static_cast<SerializationTag>(m_buffer[m_position++]);
531        return true;
532    }
533
534    bool readString(v8::Handle<v8::Value>* value)
535    {
536        uint32_t length;
537        if (!doReadUint32(&length))
538            return false;
539        if (m_position + length > m_length)
540            return false;
541        *value = v8::String::New(m_buffer + m_position, length);
542        m_position += length;
543        return true;
544    }
545
546    bool readInt32(v8::Handle<v8::Value>* value)
547    {
548        uint32_t rawValue;
549        if (!doReadUint32(&rawValue))
550            return false;
551        *value = v8::Integer::New(static_cast<int32_t>(ZigZag::decode(rawValue)));
552        return true;
553    }
554
555    bool readNumber(v8::Handle<v8::Value>* value)
556    {
557        if (m_position + sizeof(double) > m_length)
558            return false;
559        double number;
560        char* numberAsByteArray = reinterpret_cast<char*>(&number);
561        for (unsigned i = 0; i < sizeof(double); ++i)
562            numberAsByteArray[i] = m_buffer[m_position++];
563        *value = v8::Number::New(number);
564        return true;
565    }
566
567    bool doReadUint32(uint32_t* value)
568    {
569        *value = 0;
570        char currentByte;
571        int shift = 0;
572        do {
573            if (m_position >= m_length)
574                return false;
575            currentByte = m_buffer[m_position++];
576            *value |= ((currentByte & varIntMask) << shift);
577            shift += varIntShift;
578        } while (currentByte & (1 << varIntShift));
579        return true;
580    }
581
582    const char* m_buffer;
583    const unsigned m_length;
584    unsigned m_position;
585};
586
587class Deserializer {
588public:
589    explicit Deserializer(Reader& reader) : m_reader(reader)
590    {
591    }
592
593    v8::Local<v8::Value> deserialize()
594    {
595        v8::HandleScope scope;
596        while (!m_reader.isEof()) {
597            if (!doDeserialize())
598                return v8::Local<v8::Value>();
599        }
600        if (stackDepth() != 1)
601            return v8::Local<v8::Value>();
602        return scope.Close(element(0));
603    }
604
605private:
606    bool doDeserialize()
607    {
608        SerializationTag tag;
609        v8::Local<v8::Value> value;
610        int length = 0;
611        if (!m_reader.read(&tag, &value, &length))
612            return false;
613        if (!value.IsEmpty()) {
614            push(value);
615        } else if (tag == ObjectTag) {
616            if (length > stackDepth())
617                return false;
618            v8::Local<v8::Object> object = v8::Object::New();
619            for (int i = stackDepth() - length; i < stackDepth(); i += 2) {
620                v8::Local<v8::Value> propertyName = element(i);
621                v8::Local<v8::Value> propertyValue = element(i + 1);
622                object->Set(propertyName, propertyValue);
623            }
624            pop(length);
625            push(object);
626        } else if (tag == ArrayTag) {
627            if (length > stackDepth())
628                return false;
629            v8::Local<v8::Array> array = v8::Array::New(length);
630            const int depth = stackDepth() - length;
631            {
632                v8::HandleScope scope;
633                for (int i = 0; i < length; ++i)
634                    array->Set(v8::Integer::New(i), element(depth + i));
635            }
636            pop(length);
637            push(array);
638        } else if (tag != PaddingTag)
639            return false;
640        return true;
641    }
642
643    void push(v8::Local<v8::Value> value) { m_stack.append(value); }
644
645    void pop(unsigned length)
646    {
647        ASSERT(length <= m_stack.size());
648        m_stack.shrink(m_stack.size() - length);
649    }
650
651    int stackDepth() const { return m_stack.size(); }
652
653    v8::Local<v8::Value> element(unsigned index)
654    {
655        ASSERT(index < m_stack.size());
656        return m_stack[index];
657    }
658
659    Reader& m_reader;
660    Vector<v8::Local<v8::Value> > m_stack;
661};
662
663} // namespace
664
665SerializedScriptValue::SerializedScriptValue(v8::Handle<v8::Value> value)
666{
667    Writer writer;
668    Serializer serializer(writer);
669    if (!serializer.serialize(value)) {
670        // FIXME: throw exception
671        return;
672    }
673    m_data = StringImpl::adopt(writer.data());
674}
675
676SerializedScriptValue::SerializedScriptValue(String data, StringDataMode mode)
677{
678    if (mode == WireData)
679        m_data = data;
680    else {
681        ASSERT(mode == StringValue);
682        RefPtr<SharedBuffer> buffer = utf8Buffer(data);
683        Writer writer;
684        writer.writeString(buffer->data(), buffer->size());
685        m_data = StringImpl::adopt(writer.data());
686    }
687}
688
689v8::Local<v8::Value> SerializedScriptValue::deserialize()
690{
691    if (!m_data.impl())
692        return v8::Local<v8::Value>();
693    COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes);
694    Reader reader(reinterpret_cast<const char*>(m_data.impl()->characters()), 2 * m_data.length());
695    Deserializer deserializer(reader);
696    return deserializer.deserialize();
697}
698
699} // namespace WebCore
700