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 COMPUTER, 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 COMPUTER, 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
27#include "config.h"
28#include "SerializedScriptValue.h"
29
30#include "Blob.h"
31#include "File.h"
32#include "FileList.h"
33#include "ImageData.h"
34#include "JSBlob.h"
35#include "JSDOMGlobalObject.h"
36#include "JSFile.h"
37#include "JSFileList.h"
38#include "JSImageData.h"
39#include "JSNavigator.h"
40#include "SharedBuffer.h"
41#include <limits>
42#include <JavaScriptCore/APICast.h>
43#include <JavaScriptCore/APIShims.h>
44#include <runtime/DateInstance.h>
45#include <runtime/Error.h>
46#include <runtime/ExceptionHelpers.h>
47#include <runtime/PropertyNameArray.h>
48#include <runtime/RegExp.h>
49#include <runtime/RegExpObject.h>
50#include <wtf/ByteArray.h>
51#include <wtf/HashTraits.h>
52#include <wtf/Vector.h>
53
54using namespace JSC;
55using namespace std;
56
57#if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) || CPU(NEEDS_ALIGNED_ACCESS)
58#define ASSUME_LITTLE_ENDIAN 0
59#else
60#define ASSUME_LITTLE_ENDIAN 1
61#endif
62
63namespace WebCore {
64
65static const unsigned maximumFilterRecursion = 40000;
66
67enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember,
68    ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
69
70// These can't be reordered, and any new types must be added to the end of the list
71enum SerializationTag {
72    ArrayTag = 1,
73    ObjectTag = 2,
74    UndefinedTag = 3,
75    NullTag = 4,
76    IntTag = 5,
77    ZeroTag = 6,
78    OneTag = 7,
79    FalseTag = 8,
80    TrueTag = 9,
81    DoubleTag = 10,
82    DateTag = 11,
83    FileTag = 12,
84    FileListTag = 13,
85    ImageDataTag = 14,
86    BlobTag = 15,
87    StringTag = 16,
88    EmptyStringTag = 17,
89    RegExpTag = 18,
90    ObjectReferenceTag = 19,
91    ErrorTag = 255
92};
93
94/* CurrentVersion tracks the serialization version so that persistant stores
95 * are able to correctly bail out in the case of encountering newer formats.
96 *
97 * Initial version was 1.
98 * Version 2. added the ObjectReferenceTag and support for serialization of cyclic graphs.
99 */
100static const unsigned int CurrentVersion = 2;
101static const unsigned int TerminatorTag = 0xFFFFFFFF;
102static const unsigned int StringPoolTag = 0xFFFFFFFE;
103
104/*
105 * Object serialization is performed according to the following grammar, all tags
106 * are recorded as a single uint8_t.
107 *
108 * IndexType (used for the object pool and StringData's constant pool) is the
109 * minimum sized unsigned integer type required to represent the maximum index
110 * in the constant pool.
111 *
112 * SerializedValue :- <CurrentVersion:uint32_t> Value
113 * Value :- Array | Object | Terminal
114 *
115 * Array :-
116 *     ArrayTag <length:uint32_t>(<index:uint32_t><value:Value>)* TerminatorTag
117 *
118 * Object :-
119 *     ObjectTag (<name:StringData><value:Value>)* TerminatorTag
120 *
121 * Terminal :-
122 *      UndefinedTag
123 *    | NullTag
124 *    | IntTag <value:int32_t>
125 *    | ZeroTag
126 *    | OneTag
127 *    | DoubleTag <value:double>
128 *    | DateTag <value:double>
129 *    | String
130 *    | EmptyStringTag
131 *    | File
132 *    | FileList
133 *    | ImageData
134 *    | Blob
135 *    | ObjectReferenceTag <opIndex:IndexType>
136 *
137 * String :-
138 *      EmptyStringTag
139 *      StringTag StringData
140 *
141 * StringData :-
142 *      StringPoolTag <cpIndex:IndexType>
143 *      (not (TerminatorTag | StringPoolTag))<length:uint32_t><characters:UChar{length}> // Added to constant pool when seen, string length 0xFFFFFFFF is disallowed
144 *
145 * File :-
146 *    FileTag FileData
147 *
148 * FileData :-
149 *    <path:StringData> <url:StringData> <type:StringData>
150 *
151 * FileList :-
152 *    FileListTag <length:uint32_t>(<file:FileData>){length}
153 *
154 * ImageData :-
155 *    ImageDataTag <width:int32_t><height:int32_t><length:uint32_t><data:uint8_t{length}>
156 *
157 * Blob :-
158 *    BlobTag <url:StringData><type:StringData><size:long long>
159 *
160 * RegExp :-
161 *    RegExpTag <pattern:StringData><flags:StringData>
162 */
163
164typedef pair<JSC::JSValue, SerializationReturnCode> DeserializationResult;
165
166class CloneBase {
167protected:
168    CloneBase(ExecState* exec)
169        : m_exec(exec)
170        , m_failed(false)
171        , m_timeoutChecker(exec->globalData().timeoutChecker)
172    {
173    }
174
175    bool shouldTerminate()
176    {
177        return m_exec->hadException();
178    }
179
180    unsigned ticksUntilNextCheck()
181    {
182        return m_timeoutChecker.ticksUntilNextCheck();
183    }
184
185    bool didTimeOut()
186    {
187        return m_timeoutChecker.didTimeOut(m_exec);
188    }
189
190    void throwStackOverflow()
191    {
192        throwError(m_exec, createStackOverflowError(m_exec));
193    }
194
195    void throwInterruptedException()
196    {
197        throwError(m_exec, createInterruptedExecutionException(&m_exec->globalData()));
198    }
199
200    void fail()
201    {
202        ASSERT_NOT_REACHED();
203        m_failed = true;
204    }
205
206    ExecState* m_exec;
207    bool m_failed;
208    TimeoutChecker m_timeoutChecker;
209    MarkedArgumentBuffer m_gcBuffer;
210};
211
212#if ASSUME_LITTLE_ENDIAN
213template <typename T> static void writeLittleEndian(Vector<uint8_t>& buffer, T value)
214{
215    buffer.append(reinterpret_cast<uint8_t*>(&value), sizeof(value));
216}
217#else
218template <typename T> static void writeLittleEndian(Vector<uint8_t>& buffer, T value)
219{
220    for (unsigned i = 0; i < sizeof(T); i++) {
221        buffer.append(value & 0xFF);
222        value >>= 8;
223    }
224}
225#endif
226
227template <> void writeLittleEndian<uint8_t>(Vector<uint8_t>& buffer, uint8_t value)
228{
229    buffer.append(value);
230}
231
232template <typename T> static bool writeLittleEndian(Vector<uint8_t>& buffer, const T* values, uint32_t length)
233{
234    if (length > numeric_limits<uint32_t>::max() / sizeof(T))
235        return false;
236
237#if ASSUME_LITTLE_ENDIAN
238    buffer.append(reinterpret_cast<const uint8_t*>(values), length * sizeof(T));
239#else
240    for (unsigned i = 0; i < length; i++) {
241        T value = values[i];
242        for (unsigned j = 0; j < sizeof(T); j++) {
243            buffer.append(static_cast<uint8_t>(value & 0xFF));
244            value >>= 8;
245        }
246    }
247#endif
248    return true;
249}
250
251class CloneSerializer : CloneBase {
252public:
253    static SerializationReturnCode serialize(ExecState* exec, JSValue value, Vector<uint8_t>& out)
254    {
255        CloneSerializer serializer(exec, out);
256        return serializer.serialize(value);
257    }
258
259    static bool serialize(String s, Vector<uint8_t>& out)
260    {
261        writeLittleEndian(out, CurrentVersion);
262        if (s.isEmpty()) {
263            writeLittleEndian<uint8_t>(out, EmptyStringTag);
264            return true;
265        }
266        writeLittleEndian<uint8_t>(out, StringTag);
267        writeLittleEndian(out, s.length());
268        return writeLittleEndian(out, s.impl()->characters(), s.length());
269    }
270
271private:
272    CloneSerializer(ExecState* exec, Vector<uint8_t>& out)
273        : CloneBase(exec)
274        , m_buffer(out)
275        , m_emptyIdentifier(exec, UString("", 0))
276    {
277        write(CurrentVersion);
278    }
279
280    SerializationReturnCode serialize(JSValue in);
281
282    bool isArray(JSValue value)
283    {
284        if (!value.isObject())
285            return false;
286        JSObject* object = asObject(value);
287        return isJSArray(&m_exec->globalData(), object) || object->inherits(&JSArray::s_info);
288    }
289
290    bool startObjectInternal(JSObject* object)
291    {
292        // Record object for graph reconstruction
293        pair<ObjectPool::iterator, bool> iter = m_objectPool.add(object, m_objectPool.size());
294
295        // Handle duplicate references
296        if (!iter.second) {
297            write(ObjectReferenceTag);
298            ASSERT(static_cast<int32_t>(iter.first->second) < m_objectPool.size());
299            writeObjectIndex(iter.first->second);
300            return false;
301        }
302
303        m_gcBuffer.append(object);
304        return true;
305    }
306
307    bool startObject(JSObject* object)
308    {
309        if (!startObjectInternal(object))
310            return false;
311        write(ObjectTag);
312        return true;
313    }
314
315    bool startArray(JSArray* array)
316    {
317        if (!startObjectInternal(array))
318            return false;
319
320        unsigned length = array->length();
321        write(ArrayTag);
322        write(length);
323        return true;
324    }
325
326    void endObject()
327    {
328        write(TerminatorTag);
329    }
330
331    JSValue getSparseIndex(JSArray* array, unsigned propertyName, bool& hasIndex)
332    {
333        PropertySlot slot(array);
334        if (isJSArray(&m_exec->globalData(), array)) {
335            if (array->JSArray::getOwnPropertySlot(m_exec, propertyName, slot)) {
336                hasIndex = true;
337                return slot.getValue(m_exec, propertyName);
338            }
339        } else if (array->getOwnPropertySlot(m_exec, propertyName, slot)) {
340            hasIndex = true;
341            return slot.getValue(m_exec, propertyName);
342        }
343        hasIndex = false;
344        return jsNull();
345    }
346
347    JSValue getProperty(JSObject* object, const Identifier& propertyName)
348    {
349        PropertySlot slot(object);
350        if (object->getOwnPropertySlot(m_exec, propertyName, slot))
351            return slot.getValue(m_exec, propertyName);
352        return JSValue();
353    }
354
355    void dumpImmediate(JSValue value)
356    {
357        if (value.isNull())
358            write(NullTag);
359        else if (value.isUndefined())
360            write(UndefinedTag);
361        else if (value.isNumber()) {
362            if (value.isInt32()) {
363                if (!value.asInt32())
364                    write(ZeroTag);
365                else if (value.asInt32() == 1)
366                    write(OneTag);
367                else {
368                    write(IntTag);
369                    write(static_cast<uint32_t>(value.asInt32()));
370                }
371            } else {
372                write(DoubleTag);
373                write(value.asDouble());
374            }
375        } else if (value.isBoolean()) {
376            if (value.isTrue())
377                write(TrueTag);
378            else
379                write(FalseTag);
380        }
381    }
382
383    void dumpString(UString str)
384    {
385        if (str.isEmpty())
386            write(EmptyStringTag);
387        else {
388            write(StringTag);
389            write(str);
390        }
391    }
392
393    bool dumpIfTerminal(JSValue value)
394    {
395        if (!value.isCell()) {
396            dumpImmediate(value);
397            return true;
398        }
399
400        if (value.isString()) {
401            UString str = asString(value)->value(m_exec);
402            dumpString(str);
403            return true;
404        }
405
406        if (value.isNumber()) {
407            write(DoubleTag);
408            write(value.uncheckedGetNumber());
409            return true;
410        }
411
412        if (value.isObject() && asObject(value)->inherits(&DateInstance::s_info)) {
413            write(DateTag);
414            write(asDateInstance(value)->internalNumber());
415            return true;
416        }
417
418        if (isArray(value))
419            return false;
420
421        // Object cannot be serialized because the act of walking the object creates new objects
422        if (value.isObject() && asObject(value)->inherits(&JSNavigator::s_info)) {
423            fail();
424            write(NullTag);
425            return true;
426        }
427
428        if (value.isObject()) {
429            JSObject* obj = asObject(value);
430            if (obj->inherits(&JSFile::s_info)) {
431                write(FileTag);
432                write(toFile(obj));
433                return true;
434            }
435            if (obj->inherits(&JSFileList::s_info)) {
436                FileList* list = toFileList(obj);
437                write(FileListTag);
438                unsigned length = list->length();
439                write(length);
440                for (unsigned i = 0; i < length; i++)
441                    write(list->item(i));
442                return true;
443            }
444            if (obj->inherits(&JSBlob::s_info)) {
445                write(BlobTag);
446                Blob* blob = toBlob(obj);
447                write(blob->url());
448                write(blob->type());
449                write(blob->size());
450                return true;
451            }
452            if (obj->inherits(&JSImageData::s_info)) {
453                ImageData* data = toImageData(obj);
454                write(ImageDataTag);
455                write(data->width());
456                write(data->height());
457                write(data->data()->length());
458                write(data->data()->data()->data(), data->data()->length());
459                return true;
460            }
461            if (obj->inherits(&RegExpObject::s_info)) {
462                RegExpObject* regExp = asRegExpObject(obj);
463                char flags[3];
464                int flagCount = 0;
465                if (regExp->regExp()->global())
466                    flags[flagCount++] = 'g';
467                if (regExp->regExp()->ignoreCase())
468                    flags[flagCount++] = 'i';
469                if (regExp->regExp()->multiline())
470                    flags[flagCount++] = 'm';
471                write(RegExpTag);
472                write(regExp->regExp()->pattern());
473                write(UString(flags, flagCount));
474                return true;
475            }
476
477            CallData unusedData;
478            if (getCallData(value, unusedData) == CallTypeNone)
479                return false;
480        }
481        // Any other types are expected to serialize as null.
482        write(NullTag);
483        return true;
484    }
485
486    void write(SerializationTag tag)
487    {
488        writeLittleEndian<uint8_t>(m_buffer, static_cast<uint8_t>(tag));
489    }
490
491    void write(uint8_t c)
492    {
493        writeLittleEndian(m_buffer, c);
494    }
495
496    void write(uint32_t i)
497    {
498        writeLittleEndian(m_buffer, i);
499    }
500
501    void write(double d)
502    {
503        union {
504            double d;
505            int64_t i;
506        } u;
507        u.d = d;
508        writeLittleEndian(m_buffer, u.i);
509    }
510
511    void write(int32_t i)
512    {
513        writeLittleEndian(m_buffer, i);
514    }
515
516    void write(unsigned long long i)
517    {
518        writeLittleEndian(m_buffer, i);
519    }
520
521    void write(uint16_t ch)
522    {
523        writeLittleEndian(m_buffer, ch);
524    }
525
526    void writeStringIndex(unsigned i)
527    {
528        writeConstantPoolIndex(m_constantPool, i);
529    }
530
531    void writeObjectIndex(unsigned i)
532    {
533        writeConstantPoolIndex(m_objectPool, i);
534    }
535
536    template <class T> void writeConstantPoolIndex(const T& constantPool, unsigned i)
537    {
538        ASSERT(static_cast<int32_t>(i) < constantPool.size());
539        if (constantPool.size() <= 0xFF)
540            write(static_cast<uint8_t>(i));
541        else if (constantPool.size() <= 0xFFFF)
542            write(static_cast<uint16_t>(i));
543        else
544            write(static_cast<uint32_t>(i));
545    }
546
547    void write(const Identifier& ident)
548    {
549        UString str = ident.ustring();
550        pair<StringConstantPool::iterator, bool> iter = m_constantPool.add(str.impl(), m_constantPool.size());
551        if (!iter.second) {
552            write(StringPoolTag);
553            writeStringIndex(iter.first->second);
554            return;
555        }
556
557        // This condition is unlikely to happen as they would imply an ~8gb
558        // string but we should guard against it anyway
559        if (str.length() >= StringPoolTag) {
560            fail();
561            return;
562        }
563
564        // Guard against overflow
565        if (str.length() > (numeric_limits<uint32_t>::max() - sizeof(uint32_t)) / sizeof(UChar)) {
566            fail();
567            return;
568        }
569
570        writeLittleEndian<uint32_t>(m_buffer, str.length());
571        if (!writeLittleEndian<uint16_t>(m_buffer, reinterpret_cast<const uint16_t*>(str.characters()), str.length()))
572            fail();
573    }
574
575    void write(const UString& str)
576    {
577        if (str.isNull())
578            write(m_emptyIdentifier);
579        else
580            write(Identifier(m_exec, str));
581    }
582
583    void write(const String& str)
584    {
585        if (str.isEmpty())
586            write(m_emptyIdentifier);
587        else
588            write(Identifier(m_exec, str.impl()));
589    }
590
591    void write(const File* file)
592    {
593        write(file->path());
594        write(file->url());
595        write(file->type());
596    }
597
598    void write(const uint8_t* data, unsigned length)
599    {
600        m_buffer.append(data, length);
601    }
602
603    Vector<uint8_t>& m_buffer;
604    typedef HashMap<JSObject*, uint32_t> ObjectPool;
605    ObjectPool m_objectPool;
606    typedef HashMap<RefPtr<StringImpl>, uint32_t, IdentifierRepHash> StringConstantPool;
607    StringConstantPool m_constantPool;
608    Identifier m_emptyIdentifier;
609};
610
611SerializationReturnCode CloneSerializer::serialize(JSValue in)
612{
613    Vector<uint32_t, 16> indexStack;
614    Vector<uint32_t, 16> lengthStack;
615    Vector<PropertyNameArray, 16> propertyStack;
616    Vector<JSObject*, 16> inputObjectStack;
617    Vector<JSArray*, 16> inputArrayStack;
618    Vector<WalkerState, 16> stateStack;
619    WalkerState state = StateUnknown;
620    JSValue inValue = in;
621    unsigned tickCount = ticksUntilNextCheck();
622    while (1) {
623        switch (state) {
624            arrayStartState:
625            case ArrayStartState: {
626                ASSERT(isArray(inValue));
627                if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion)
628                    return StackOverflowError;
629
630                JSArray* inArray = asArray(inValue);
631                unsigned length = inArray->length();
632                if (!startArray(inArray))
633                    break;
634                inputArrayStack.append(inArray);
635                indexStack.append(0);
636                lengthStack.append(length);
637                // fallthrough
638            }
639            arrayStartVisitMember:
640            case ArrayStartVisitMember: {
641                if (!--tickCount) {
642                    if (didTimeOut())
643                        return InterruptedExecutionError;
644                    tickCount = ticksUntilNextCheck();
645                }
646
647                JSArray* array = inputArrayStack.last();
648                uint32_t index = indexStack.last();
649                if (index == lengthStack.last()) {
650                    endObject();
651                    inputArrayStack.removeLast();
652                    indexStack.removeLast();
653                    lengthStack.removeLast();
654                    break;
655                }
656                if (array->canGetIndex(index))
657                    inValue = array->getIndex(index);
658                else {
659                    bool hasIndex = false;
660                    inValue = getSparseIndex(array, index, hasIndex);
661                    if (!hasIndex) {
662                        indexStack.last()++;
663                        goto arrayStartVisitMember;
664                    }
665                }
666
667                write(index);
668                if (dumpIfTerminal(inValue)) {
669                    indexStack.last()++;
670                    goto arrayStartVisitMember;
671                }
672                stateStack.append(ArrayEndVisitMember);
673                goto stateUnknown;
674            }
675            case ArrayEndVisitMember: {
676                indexStack.last()++;
677                goto arrayStartVisitMember;
678            }
679            objectStartState:
680            case ObjectStartState: {
681                ASSERT(inValue.isObject());
682                if (inputObjectStack.size() + inputArrayStack.size() > maximumFilterRecursion)
683                    return StackOverflowError;
684                JSObject* inObject = asObject(inValue);
685                if (!startObject(inObject))
686                    break;
687                inputObjectStack.append(inObject);
688                indexStack.append(0);
689                propertyStack.append(PropertyNameArray(m_exec));
690                inObject->getOwnPropertyNames(m_exec, propertyStack.last());
691                // fallthrough
692            }
693            objectStartVisitMember:
694            case ObjectStartVisitMember: {
695                if (!--tickCount) {
696                    if (didTimeOut())
697                        return InterruptedExecutionError;
698                    tickCount = ticksUntilNextCheck();
699                }
700
701                JSObject* object = inputObjectStack.last();
702                uint32_t index = indexStack.last();
703                PropertyNameArray& properties = propertyStack.last();
704                if (index == properties.size()) {
705                    endObject();
706                    inputObjectStack.removeLast();
707                    indexStack.removeLast();
708                    propertyStack.removeLast();
709                    break;
710                }
711                inValue = getProperty(object, properties[index]);
712                if (shouldTerminate())
713                    return ExistingExceptionError;
714
715                if (!inValue) {
716                    // Property was removed during serialisation
717                    indexStack.last()++;
718                    goto objectStartVisitMember;
719                }
720                write(properties[index]);
721
722                if (shouldTerminate())
723                    return ExistingExceptionError;
724
725                if (!dumpIfTerminal(inValue)) {
726                    stateStack.append(ObjectEndVisitMember);
727                    goto stateUnknown;
728                }
729                // fallthrough
730            }
731            case ObjectEndVisitMember: {
732                if (shouldTerminate())
733                    return ExistingExceptionError;
734
735                indexStack.last()++;
736                goto objectStartVisitMember;
737            }
738            stateUnknown:
739            case StateUnknown:
740                if (dumpIfTerminal(inValue))
741                    break;
742
743                if (isArray(inValue))
744                    goto arrayStartState;
745                goto objectStartState;
746        }
747        if (stateStack.isEmpty())
748            break;
749
750        state = stateStack.last();
751        stateStack.removeLast();
752
753        if (!--tickCount) {
754            if (didTimeOut())
755                return InterruptedExecutionError;
756            tickCount = ticksUntilNextCheck();
757        }
758    }
759    if (m_failed)
760        return UnspecifiedError;
761
762    return SuccessfullyCompleted;
763}
764
765class CloneDeserializer : CloneBase {
766public:
767    static String deserializeString(const Vector<uint8_t>& buffer)
768    {
769        const uint8_t* ptr = buffer.begin();
770        const uint8_t* end = buffer.end();
771        uint32_t version;
772        if (!readLittleEndian(ptr, end, version) || version > CurrentVersion)
773            return String();
774        uint8_t tag;
775        if (!readLittleEndian(ptr, end, tag) || tag != StringTag)
776            return String();
777        uint32_t length;
778        if (!readLittleEndian(ptr, end, length) || length >= StringPoolTag)
779            return String();
780        UString str;
781        if (!readString(ptr, end, str, length))
782            return String();
783        return String(str.impl());
784    }
785
786    static DeserializationResult deserialize(ExecState* exec, JSGlobalObject* globalObject, const Vector<uint8_t>& buffer)
787    {
788        if (!buffer.size())
789            return make_pair(jsNull(), UnspecifiedError);
790        CloneDeserializer deserializer(exec, globalObject, buffer);
791        if (!deserializer.isValid())
792            return make_pair(JSValue(), ValidationError);
793        return deserializer.deserialize();
794    }
795
796private:
797    struct CachedString {
798        CachedString(const UString& string)
799            : m_string(string)
800        {
801        }
802
803        JSValue jsString(ExecState* exec)
804        {
805            if (!m_jsString)
806                m_jsString = JSC::jsString(exec, m_string);
807            return m_jsString;
808        }
809        const UString& ustring() { return m_string; }
810
811    private:
812        UString m_string;
813        JSValue m_jsString;
814    };
815
816    struct CachedStringRef {
817        CachedStringRef()
818            : m_base(0)
819            , m_index(0)
820        {
821        }
822        CachedStringRef(Vector<CachedString>* base, size_t index)
823            : m_base(base)
824            , m_index(index)
825        {
826        }
827
828        CachedString* operator->() { ASSERT(m_base); return &m_base->at(m_index); }
829
830    private:
831        Vector<CachedString>* m_base;
832        size_t m_index;
833    };
834
835    CloneDeserializer(ExecState* exec, JSGlobalObject* globalObject, const Vector<uint8_t>& buffer)
836        : CloneBase(exec)
837        , m_globalObject(globalObject)
838        , m_isDOMGlobalObject(globalObject->inherits(&JSDOMGlobalObject::s_info))
839        , m_ptr(buffer.data())
840        , m_end(buffer.data() + buffer.size())
841        , m_version(0xFFFFFFFF)
842    {
843        if (!read(m_version))
844            m_version = 0xFFFFFFFF;
845    }
846
847    DeserializationResult deserialize();
848
849    void throwValidationError()
850    {
851        throwError(m_exec, createTypeError(m_exec, "Unable to deserialize data."));
852    }
853
854    bool isValid() const { return m_version <= CurrentVersion; }
855
856    template <typename T> bool readLittleEndian(T& value)
857    {
858        if (m_failed || !readLittleEndian(m_ptr, m_end, value)) {
859            fail();
860            return false;
861        }
862        return true;
863    }
864#if ASSUME_LITTLE_ENDIAN
865    template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
866    {
867        if (ptr > end - sizeof(value))
868            return false;
869
870        if (sizeof(T) == 1)
871            value = *ptr++;
872        else {
873            value = *reinterpret_cast<const T*>(ptr);
874            ptr += sizeof(T);
875        }
876        return true;
877    }
878#else
879    template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
880    {
881        if (ptr > end - sizeof(value))
882            return false;
883
884        if (sizeof(T) == 1)
885            value = *ptr++;
886        else {
887            value = 0;
888            for (unsigned i = 0; i < sizeof(T); i++)
889                value += ((T)*ptr++) << (i * 8);
890        }
891        return true;
892    }
893#endif
894
895    bool read(uint32_t& i)
896    {
897        return readLittleEndian(i);
898    }
899
900    bool read(int32_t& i)
901    {
902        return readLittleEndian(*reinterpret_cast<uint32_t*>(&i));
903    }
904
905    bool read(uint16_t& i)
906    {
907        return readLittleEndian(i);
908    }
909
910    bool read(uint8_t& i)
911    {
912        return readLittleEndian(i);
913    }
914
915    bool read(double& d)
916    {
917        union {
918            double d;
919            uint64_t i64;
920        } u;
921        if (!readLittleEndian(u.i64))
922            return false;
923        d = u.d;
924        return true;
925    }
926
927    bool read(unsigned long long& i)
928    {
929        return readLittleEndian(i);
930    }
931
932    bool readStringIndex(uint32_t& i)
933    {
934        return readConstantPoolIndex(m_constantPool, i);
935    }
936
937    template <class T> bool readConstantPoolIndex(const T& constantPool, uint32_t& i)
938    {
939        if (constantPool.size() <= 0xFF) {
940            uint8_t i8;
941            if (!read(i8))
942                return false;
943            i = i8;
944            return true;
945        }
946        if (constantPool.size() <= 0xFFFF) {
947            uint16_t i16;
948            if (!read(i16))
949                return false;
950            i = i16;
951            return true;
952        }
953        return read(i);
954    }
955
956    static bool readString(const uint8_t*& ptr, const uint8_t* end, UString& str, unsigned length)
957    {
958        if (length >= numeric_limits<int32_t>::max() / sizeof(UChar))
959            return false;
960
961        unsigned size = length * sizeof(UChar);
962        if ((end - ptr) < static_cast<int>(size))
963            return false;
964
965#if ASSUME_LITTLE_ENDIAN
966        str = UString(reinterpret_cast<const UChar*>(ptr), length);
967        ptr += length * sizeof(UChar);
968#else
969        Vector<UChar> buffer;
970        buffer.reserveCapacity(length);
971        for (unsigned i = 0; i < length; i++) {
972            uint16_t ch;
973            readLittleEndian(ptr, end, ch);
974            buffer.append(ch);
975        }
976        str = UString::adopt(buffer);
977#endif
978        return true;
979    }
980
981    bool readStringData(CachedStringRef& cachedString)
982    {
983        bool scratch;
984        return readStringData(cachedString, scratch);
985    }
986
987    bool readStringData(CachedStringRef& cachedString, bool& wasTerminator)
988    {
989        if (m_failed)
990            return false;
991        uint32_t length = 0;
992        if (!read(length))
993            return false;
994        if (length == TerminatorTag) {
995            wasTerminator = true;
996            return false;
997        }
998        if (length == StringPoolTag) {
999            unsigned index = 0;
1000            if (!readStringIndex(index)) {
1001                fail();
1002                return false;
1003            }
1004            if (index >= m_constantPool.size()) {
1005                fail();
1006                return false;
1007            }
1008            cachedString = CachedStringRef(&m_constantPool, index);
1009            return true;
1010        }
1011        UString str;
1012        if (!readString(m_ptr, m_end, str, length)) {
1013            fail();
1014            return false;
1015        }
1016        m_constantPool.append(str);
1017        cachedString = CachedStringRef(&m_constantPool, m_constantPool.size() - 1);
1018        return true;
1019    }
1020
1021    SerializationTag readTag()
1022    {
1023        if (m_ptr >= m_end)
1024            return ErrorTag;
1025        return static_cast<SerializationTag>(*m_ptr++);
1026    }
1027
1028    void putProperty(JSArray* array, unsigned index, JSValue value)
1029    {
1030        if (array->canSetIndex(index))
1031            array->setIndex(m_exec->globalData(), index, value);
1032        else
1033            array->put(m_exec, index, value);
1034    }
1035
1036    void putProperty(JSObject* object, const Identifier& property, JSValue value)
1037    {
1038        object->putDirect(m_exec->globalData(), property, value);
1039    }
1040
1041    bool readFile(RefPtr<File>& file)
1042    {
1043        CachedStringRef path;
1044        if (!readStringData(path))
1045            return 0;
1046        CachedStringRef url;
1047        if (!readStringData(url))
1048            return 0;
1049        CachedStringRef type;
1050        if (!readStringData(type))
1051            return 0;
1052        if (m_isDOMGlobalObject)
1053            file = File::create(String(path->ustring().impl()), KURL(KURL(), String(url->ustring().impl())), String(type->ustring().impl()));
1054        return true;
1055    }
1056
1057    JSValue readTerminal()
1058    {
1059        SerializationTag tag = readTag();
1060        switch (tag) {
1061        case UndefinedTag:
1062            return jsUndefined();
1063        case NullTag:
1064            return jsNull();
1065        case IntTag: {
1066            int32_t i;
1067            if (!read(i))
1068                return JSValue();
1069            return jsNumber(i);
1070        }
1071        case ZeroTag:
1072            return jsNumber(0);
1073        case OneTag:
1074            return jsNumber(1);
1075        case FalseTag:
1076            return jsBoolean(false);
1077        case TrueTag:
1078            return jsBoolean(true);
1079        case DoubleTag: {
1080            double d;
1081            if (!read(d))
1082                return JSValue();
1083            return jsNumber(d);
1084        }
1085        case DateTag: {
1086            double d;
1087            if (!read(d))
1088                return JSValue();
1089            return new (m_exec) DateInstance(m_exec, m_globalObject->dateStructure(), d);
1090        }
1091        case FileTag: {
1092            RefPtr<File> file;
1093            if (!readFile(file))
1094                return JSValue();
1095            if (!m_isDOMGlobalObject)
1096                return jsNull();
1097            return toJS(m_exec, static_cast<JSDOMGlobalObject*>(m_globalObject), file.get());
1098        }
1099        case FileListTag: {
1100            unsigned length = 0;
1101            if (!read(length))
1102                return JSValue();
1103            RefPtr<FileList> result = FileList::create();
1104            for (unsigned i = 0; i < length; i++) {
1105                RefPtr<File> file;
1106                if (!readFile(file))
1107                    return JSValue();
1108                if (m_isDOMGlobalObject)
1109                    result->append(file.get());
1110            }
1111            if (!m_isDOMGlobalObject)
1112                return jsNull();
1113            return toJS(m_exec, static_cast<JSDOMGlobalObject*>(m_globalObject), result.get());
1114        }
1115        case ImageDataTag: {
1116            int32_t width;
1117            if (!read(width))
1118                return JSValue();
1119            int32_t height;
1120            if (!read(height))
1121                return JSValue();
1122            uint32_t length;
1123            if (!read(length))
1124                return JSValue();
1125            if (m_end < ((uint8_t*)0) + length || m_ptr > m_end - length) {
1126                fail();
1127                return JSValue();
1128            }
1129            if (!m_isDOMGlobalObject) {
1130                m_ptr += length;
1131                return jsNull();
1132            }
1133            RefPtr<ImageData> result = ImageData::create(IntSize(width, height));
1134            memcpy(result->data()->data()->data(), m_ptr, length);
1135            m_ptr += length;
1136            return toJS(m_exec, static_cast<JSDOMGlobalObject*>(m_globalObject), result.get());
1137        }
1138        case BlobTag: {
1139            CachedStringRef url;
1140            if (!readStringData(url))
1141                return JSValue();
1142            CachedStringRef type;
1143            if (!readStringData(type))
1144                return JSValue();
1145            unsigned long long size = 0;
1146            if (!read(size))
1147                return JSValue();
1148            if (!m_isDOMGlobalObject)
1149                return jsNull();
1150            return toJS(m_exec, static_cast<JSDOMGlobalObject*>(m_globalObject), Blob::create(KURL(KURL(), url->ustring().impl()), String(type->ustring().impl()), size));
1151        }
1152        case StringTag: {
1153            CachedStringRef cachedString;
1154            if (!readStringData(cachedString))
1155                return JSValue();
1156            return cachedString->jsString(m_exec);
1157        }
1158        case EmptyStringTag:
1159            return jsEmptyString(&m_exec->globalData());
1160        case RegExpTag: {
1161            CachedStringRef pattern;
1162            if (!readStringData(pattern))
1163                return JSValue();
1164            CachedStringRef flags;
1165            if (!readStringData(flags))
1166                return JSValue();
1167            RegExpFlags reFlags = regExpFlags(flags->ustring());
1168            ASSERT(reFlags != InvalidFlags);
1169            RefPtr<RegExp> regExp = RegExp::create(&m_exec->globalData(), pattern->ustring(), reFlags);
1170            return new (m_exec) RegExpObject(m_exec->lexicalGlobalObject(), m_globalObject->regExpStructure(), regExp);
1171        }
1172        case ObjectReferenceTag: {
1173            unsigned index = 0;
1174            if (!readConstantPoolIndex(m_gcBuffer, index)) {
1175                fail();
1176                return JSValue();
1177            }
1178            return m_gcBuffer.at(index);
1179        }
1180        default:
1181            m_ptr--; // Push the tag back
1182            return JSValue();
1183        }
1184    }
1185
1186    JSGlobalObject* m_globalObject;
1187    bool m_isDOMGlobalObject;
1188    const uint8_t* m_ptr;
1189    const uint8_t* m_end;
1190    unsigned m_version;
1191    Vector<CachedString> m_constantPool;
1192};
1193
1194DeserializationResult CloneDeserializer::deserialize()
1195{
1196    Vector<uint32_t, 16> indexStack;
1197    Vector<Identifier, 16> propertyNameStack;
1198    Vector<JSObject*, 16> outputObjectStack;
1199    Vector<JSArray*, 16> outputArrayStack;
1200    Vector<WalkerState, 16> stateStack;
1201    WalkerState state = StateUnknown;
1202    JSValue outValue;
1203
1204    unsigned tickCount = ticksUntilNextCheck();
1205    while (1) {
1206        switch (state) {
1207        arrayStartState:
1208        case ArrayStartState: {
1209            uint32_t length;
1210            if (!read(length)) {
1211                fail();
1212                goto error;
1213            }
1214            JSArray* outArray = constructEmptyArray(m_exec, m_globalObject);
1215            outArray->setLength(length);
1216            m_gcBuffer.append(outArray);
1217            outputArrayStack.append(outArray);
1218            // fallthrough
1219        }
1220        arrayStartVisitMember:
1221        case ArrayStartVisitMember: {
1222            if (!--tickCount) {
1223                if (didTimeOut())
1224                    return make_pair(JSValue(), InterruptedExecutionError);
1225                tickCount = ticksUntilNextCheck();
1226            }
1227
1228            uint32_t index;
1229            if (!read(index)) {
1230                fail();
1231                goto error;
1232            }
1233            if (index == TerminatorTag) {
1234                JSArray* outArray = outputArrayStack.last();
1235                outValue = outArray;
1236                outputArrayStack.removeLast();
1237                break;
1238            }
1239
1240            if (JSValue terminal = readTerminal()) {
1241                putProperty(outputArrayStack.last(), index, terminal);
1242                goto arrayStartVisitMember;
1243            }
1244            if (m_failed)
1245                goto error;
1246            indexStack.append(index);
1247            stateStack.append(ArrayEndVisitMember);
1248            goto stateUnknown;
1249        }
1250        case ArrayEndVisitMember: {
1251            JSArray* outArray = outputArrayStack.last();
1252            putProperty(outArray, indexStack.last(), outValue);
1253            indexStack.removeLast();
1254            goto arrayStartVisitMember;
1255        }
1256        objectStartState:
1257        case ObjectStartState: {
1258            if (outputObjectStack.size() + outputArrayStack.size() > maximumFilterRecursion)
1259                return make_pair(JSValue(), StackOverflowError);
1260            JSObject* outObject = constructEmptyObject(m_exec, m_globalObject);
1261            m_gcBuffer.append(outObject);
1262            outputObjectStack.append(outObject);
1263            // fallthrough
1264        }
1265        objectStartVisitMember:
1266        case ObjectStartVisitMember: {
1267            if (!--tickCount) {
1268                if (didTimeOut())
1269                    return make_pair(JSValue(), InterruptedExecutionError);
1270                tickCount = ticksUntilNextCheck();
1271            }
1272
1273            CachedStringRef cachedString;
1274            bool wasTerminator = false;
1275            if (!readStringData(cachedString, wasTerminator)) {
1276                if (!wasTerminator)
1277                    goto error;
1278                JSObject* outObject = outputObjectStack.last();
1279                outValue = outObject;
1280                outputObjectStack.removeLast();
1281                break;
1282            }
1283
1284            if (JSValue terminal = readTerminal()) {
1285                putProperty(outputObjectStack.last(), Identifier(m_exec, cachedString->ustring()), terminal);
1286                goto objectStartVisitMember;
1287            }
1288            stateStack.append(ObjectEndVisitMember);
1289            propertyNameStack.append(Identifier(m_exec, cachedString->ustring()));
1290            goto stateUnknown;
1291        }
1292        case ObjectEndVisitMember: {
1293            putProperty(outputObjectStack.last(), propertyNameStack.last(), outValue);
1294            propertyNameStack.removeLast();
1295            goto objectStartVisitMember;
1296        }
1297        stateUnknown:
1298        case StateUnknown:
1299            if (JSValue terminal = readTerminal()) {
1300                outValue = terminal;
1301                break;
1302            }
1303            SerializationTag tag = readTag();
1304            if (tag == ArrayTag)
1305                goto arrayStartState;
1306            if (tag == ObjectTag)
1307                goto objectStartState;
1308            goto error;
1309        }
1310        if (stateStack.isEmpty())
1311            break;
1312
1313        state = stateStack.last();
1314        stateStack.removeLast();
1315
1316        if (!--tickCount) {
1317            if (didTimeOut())
1318                return make_pair(JSValue(), InterruptedExecutionError);
1319            tickCount = ticksUntilNextCheck();
1320        }
1321    }
1322    ASSERT(outValue);
1323    ASSERT(!m_failed);
1324    return make_pair(outValue, SuccessfullyCompleted);
1325error:
1326    fail();
1327    return make_pair(JSValue(), ValidationError);
1328}
1329
1330
1331
1332SerializedScriptValue::~SerializedScriptValue()
1333{
1334}
1335
1336SerializedScriptValue::SerializedScriptValue(Vector<uint8_t>& buffer)
1337{
1338    m_data.swap(buffer);
1339}
1340
1341PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(ExecState* exec, JSValue value, SerializationErrorMode throwExceptions)
1342{
1343    Vector<uint8_t> buffer;
1344    SerializationReturnCode code = CloneSerializer::serialize(exec, value, buffer);
1345    if (throwExceptions == Throwing)
1346        maybeThrowExceptionIfSerializationFailed(exec, code);
1347
1348    if (!serializationDidCompleteSuccessfully(code))
1349        return 0;
1350
1351    return adoptRef(new SerializedScriptValue(buffer));
1352}
1353
1354PassRefPtr<SerializedScriptValue> SerializedScriptValue::create()
1355{
1356    Vector<uint8_t> buffer;
1357    return adoptRef(new SerializedScriptValue(buffer));
1358}
1359
1360PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(String string)
1361{
1362    Vector<uint8_t> buffer;
1363    if (!CloneSerializer::serialize(string, buffer))
1364        return 0;
1365    return adoptRef(new SerializedScriptValue(buffer));
1366}
1367
1368PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(JSContextRef originContext, JSValueRef apiValue, JSValueRef* exception)
1369{
1370    ExecState* exec = toJS(originContext);
1371    APIEntryShim entryShim(exec);
1372    JSValue value = toJS(exec, apiValue);
1373    PassRefPtr<SerializedScriptValue> serializedValue = SerializedScriptValue::create(exec, value);
1374    if (exec->hadException()) {
1375        if (exception)
1376            *exception = toRef(exec, exec->exception());
1377        exec->clearException();
1378        return 0;
1379    }
1380    ASSERT(serializedValue);
1381    return serializedValue;
1382}
1383
1384String SerializedScriptValue::toString()
1385{
1386    return CloneDeserializer::deserializeString(m_data);
1387}
1388
1389JSValue SerializedScriptValue::deserialize(ExecState* exec, JSGlobalObject* globalObject, SerializationErrorMode throwExceptions)
1390{
1391    DeserializationResult result = CloneDeserializer::deserialize(exec, globalObject, m_data);
1392    if (throwExceptions == Throwing)
1393        maybeThrowExceptionIfSerializationFailed(exec, result.second);
1394    return result.first;
1395}
1396
1397JSValueRef SerializedScriptValue::deserialize(JSContextRef destinationContext, JSValueRef* exception)
1398{
1399    ExecState* exec = toJS(destinationContext);
1400    APIEntryShim entryShim(exec);
1401    JSValue value = deserialize(exec, exec->lexicalGlobalObject());
1402    if (exec->hadException()) {
1403        if (exception)
1404            *exception = toRef(exec, exec->exception());
1405        exec->clearException();
1406        return 0;
1407    }
1408    ASSERT(value);
1409    return toRef(exec, value);
1410}
1411
1412SerializedScriptValue* SerializedScriptValue::nullValue()
1413{
1414    DEFINE_STATIC_LOCAL(RefPtr<SerializedScriptValue>, emptyValue, (SerializedScriptValue::create()));
1415    return emptyValue.get();
1416}
1417
1418void SerializedScriptValue::maybeThrowExceptionIfSerializationFailed(ExecState* exec, SerializationReturnCode code)
1419{
1420    if (code == SuccessfullyCompleted)
1421        return;
1422
1423    switch (code) {
1424    case StackOverflowError:
1425        throwError(exec, createStackOverflowError(exec));
1426        break;
1427    case InterruptedExecutionError:
1428        throwError(exec, createInterruptedExecutionException(&exec->globalData()));
1429        break;
1430    case ValidationError:
1431        throwError(exec, createTypeError(exec, "Unable to deserialize data."));
1432        break;
1433    case ExistingExceptionError:
1434        break;
1435    case UnspecifiedError:
1436        break;
1437    default:
1438        ASSERT_NOT_REACHED();
1439    }
1440}
1441
1442bool SerializedScriptValue::serializationDidCompleteSuccessfully(SerializationReturnCode code)
1443{
1444    return (code == SuccessfullyCompleted);
1445}
1446
1447}
1448