Source/JavaScriptCore: https://bugs.webkit.org/show_bug.cgi?id=119548
[WebKit-https.git] / Source / WebCore / bindings / js / SerializedScriptValue.cpp
1 /*
2  * Copyright (C) 2009, 2013 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 "ExceptionCode.h"
32 #include "File.h"
33 #include "FileList.h"
34 #include "ImageData.h"
35 #include "JSBlob.h"
36 #include "JSDOMGlobalObject.h"
37 #include "JSFile.h"
38 #include "JSFileList.h"
39 #include "JSImageData.h"
40 #include "JSMessagePort.h"
41 #include "JSNavigator.h"
42 #include "NotImplemented.h"
43 #include "ScriptValue.h"
44 #include "SharedBuffer.h"
45 #include "WebCoreJSClientData.h"
46 #include <limits>
47 #include <JavaScriptCore/APICast.h>
48 #include <JavaScriptCore/APIShims.h>
49 #include <runtime/ArrayBuffer.h>
50 #include <runtime/BooleanObject.h>
51 #include <runtime/DateInstance.h>
52 #include <runtime/Error.h>
53 #include <runtime/ExceptionHelpers.h>
54 #include <runtime/JSArrayBuffer.h>
55 #include <runtime/JSArrayBufferView.h>
56 #include <runtime/JSDataView.h>
57 #include <runtime/JSTypedArrays.h>
58 #include <runtime/ObjectConstructor.h>
59 #include <runtime/Operations.h>
60 #include <runtime/PropertyNameArray.h>
61 #include <runtime/RegExp.h>
62 #include <runtime/RegExpObject.h>
63 #include <runtime/TypedArrayInlines.h>
64 #include <runtime/TypedArrays.h>
65 #include <wtf/HashTraits.h>
66 #include <wtf/Vector.h>
67
68 using namespace JSC;
69 using namespace std;
70
71 #if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) || CPU(NEEDS_ALIGNED_ACCESS)
72 #define ASSUME_LITTLE_ENDIAN 0
73 #else
74 #define ASSUME_LITTLE_ENDIAN 1
75 #endif
76
77 namespace WebCore {
78
79 static const unsigned maximumFilterRecursion = 40000;
80
81 enum WalkerState { StateUnknown, ArrayStartState, ArrayStartVisitMember, ArrayEndVisitMember,
82     ObjectStartState, ObjectStartVisitMember, ObjectEndVisitMember };
83
84 // These can't be reordered, and any new types must be added to the end of the list
85 enum SerializationTag {
86     ArrayTag = 1,
87     ObjectTag = 2,
88     UndefinedTag = 3,
89     NullTag = 4,
90     IntTag = 5,
91     ZeroTag = 6,
92     OneTag = 7,
93     FalseTag = 8,
94     TrueTag = 9,
95     DoubleTag = 10,
96     DateTag = 11,
97     FileTag = 12,
98     FileListTag = 13,
99     ImageDataTag = 14,
100     BlobTag = 15,
101     StringTag = 16,
102     EmptyStringTag = 17,
103     RegExpTag = 18,
104     ObjectReferenceTag = 19,
105     MessagePortReferenceTag = 20,
106     ArrayBufferTag = 21,
107     ArrayBufferViewTag = 22,
108     ArrayBufferTransferTag = 23,
109     TrueObjectTag = 24,
110     FalseObjectTag = 25,
111     StringObjectTag = 26,
112     EmptyStringObjectTag = 27,
113     NumberObjectTag = 28,
114     ErrorTag = 255
115 };
116
117 enum ArrayBufferViewSubtag {
118     DataViewTag = 0,
119     Int8ArrayTag = 1,
120     Uint8ArrayTag = 2,
121     Uint8ClampedArrayTag = 3,
122     Int16ArrayTag = 4,
123     Uint16ArrayTag = 5,
124     Int32ArrayTag = 6,
125     Uint32ArrayTag = 7,
126     Float32ArrayTag = 8,
127     Float64ArrayTag = 9
128 };
129
130 static unsigned typedArrayElementSize(ArrayBufferViewSubtag tag)
131 {
132     switch (tag) {
133     case DataViewTag:
134     case Int8ArrayTag:
135     case Uint8ArrayTag:
136     case Uint8ClampedArrayTag:
137         return 1;
138     case Int16ArrayTag:
139     case Uint16ArrayTag:
140         return 2;
141     case Int32ArrayTag:
142     case Uint32ArrayTag:
143     case Float32ArrayTag:
144         return 4;
145     case Float64ArrayTag:
146         return 8;
147     default:
148         return 0;
149     }
150
151 }
152
153 /* CurrentVersion tracks the serialization version so that persistant stores
154  * are able to correctly bail out in the case of encountering newer formats.
155  *
156  * Initial version was 1.
157  * Version 2. added the ObjectReferenceTag and support for serialization of cyclic graphs.
158  * Version 3. added the FalseObjectTag, TrueObjectTag, NumberObjectTag, StringObjectTag
159  * and EmptyStringObjectTag for serialization of Boolean, Number and String objects.
160  * Version 4. added support for serializing non-index properties of arrays.
161  */
162 static const unsigned CurrentVersion = 4;
163 static const unsigned TerminatorTag = 0xFFFFFFFF;
164 static const unsigned StringPoolTag = 0xFFFFFFFE;
165 static const unsigned NonIndexPropertiesTag = 0xFFFFFFFD;
166
167 /*
168  * Object serialization is performed according to the following grammar, all tags
169  * are recorded as a single uint8_t.
170  *
171  * IndexType (used for the object pool and StringData's constant pool) is the
172  * minimum sized unsigned integer type required to represent the maximum index
173  * in the constant pool.
174  *
175  * SerializedValue :- <CurrentVersion:uint32_t> Value
176  * Value :- Array | Object | Terminal
177  *
178  * Array :-
179  *     ArrayTag <length:uint32_t>(<index:uint32_t><value:Value>)* TerminatorTag
180  *
181  * Object :-
182  *     ObjectTag (<name:StringData><value:Value>)* TerminatorTag
183  *
184  * Terminal :-
185  *      UndefinedTag
186  *    | NullTag
187  *    | IntTag <value:int32_t>
188  *    | ZeroTag
189  *    | OneTag
190  *    | FalseTag
191  *    | TrueTag
192  *    | FalseObjectTag
193  *    | TrueObjectTag
194  *    | DoubleTag <value:double>
195  *    | NumberObjectTag <value:double>
196  *    | DateTag <value:double>
197  *    | String
198  *    | EmptyStringTag
199  *    | EmptyStringObjectTag
200  *    | File
201  *    | FileList
202  *    | ImageData
203  *    | Blob
204  *    | ObjectReference
205  *    | MessagePortReferenceTag <value:uint32_t>
206  *    | ArrayBuffer
207  *    | ArrayBufferViewTag ArrayBufferViewSubtag <byteOffset:uint32_t> <byteLenght:uint32_t> (ArrayBuffer | ObjectReference)
208  *    | ArrayBufferTransferTag <value:uint32_t>
209  *
210  * String :-
211  *      EmptyStringTag
212  *      StringTag StringData
213  *
214  * StringObject:
215  *      EmptyStringObjectTag
216  *      StringObjectTag StringData
217  *
218  * StringData :-
219  *      StringPoolTag <cpIndex:IndexType>
220  *      (not (TerminatorTag | StringPoolTag))<length:uint32_t><characters:UChar{length}> // Added to constant pool when seen, string length 0xFFFFFFFF is disallowed
221  *
222  * File :-
223  *    FileTag FileData
224  *
225  * FileData :-
226  *    <path:StringData> <url:StringData> <type:StringData>
227  *
228  * FileList :-
229  *    FileListTag <length:uint32_t>(<file:FileData>){length}
230  *
231  * ImageData :-
232  *    ImageDataTag <width:int32_t><height:int32_t><length:uint32_t><data:uint8_t{length}>
233  *
234  * Blob :-
235  *    BlobTag <url:StringData><type:StringData><size:long long>
236  *
237  * RegExp :-
238  *    RegExpTag <pattern:StringData><flags:StringData>
239  *
240  * ObjectReference :-
241  *    ObjectReferenceTag <opIndex:IndexType>
242  *
243  * ArrayBuffer :-
244  *    ArrayBufferTag <length:uint32_t> <contents:byte{length}>
245  */
246
247 typedef pair<JSC::JSValue, SerializationReturnCode> DeserializationResult;
248
249 class CloneBase {
250 protected:
251     CloneBase(ExecState* exec)
252         : m_exec(exec)
253         , m_failed(false)
254     {
255     }
256
257     bool shouldTerminate()
258     {
259         return m_exec->hadException();
260     }
261
262     void throwStackOverflow()
263     {
264         m_exec->vm().throwException(m_exec, createStackOverflowError(m_exec));
265     }
266
267     NO_RETURN_DUE_TO_ASSERT
268     void fail()
269     {
270         ASSERT_NOT_REACHED();
271         m_failed = true;
272     }
273
274     ExecState* m_exec;
275     bool m_failed;
276     MarkedArgumentBuffer m_gcBuffer;
277 };
278
279 #if ASSUME_LITTLE_ENDIAN
280 template <typename T> static void writeLittleEndian(Vector<uint8_t>& buffer, T value)
281 {
282     buffer.append(reinterpret_cast<uint8_t*>(&value), sizeof(value));
283 }
284 #else
285 template <typename T> static void writeLittleEndian(Vector<uint8_t>& buffer, T value)
286 {
287     for (unsigned i = 0; i < sizeof(T); i++) {
288         buffer.append(value & 0xFF);
289         value >>= 8;
290     }
291 }
292 #endif
293
294 template <> void writeLittleEndian<uint8_t>(Vector<uint8_t>& buffer, uint8_t value)
295 {
296     buffer.append(value);
297 }
298
299 template <typename T> static bool writeLittleEndian(Vector<uint8_t>& buffer, const T* values, uint32_t length)
300 {
301     if (length > numeric_limits<uint32_t>::max() / sizeof(T))
302         return false;
303
304 #if ASSUME_LITTLE_ENDIAN
305     buffer.append(reinterpret_cast<const uint8_t*>(values), length * sizeof(T));
306 #else
307     for (unsigned i = 0; i < length; i++) {
308         T value = values[i];
309         for (unsigned j = 0; j < sizeof(T); j++) {
310             buffer.append(static_cast<uint8_t>(value & 0xFF));
311             value >>= 8;
312         }
313     }
314 #endif
315     return true;
316 }
317
318 class CloneSerializer : CloneBase {
319 public:
320     static SerializationReturnCode serialize(ExecState* exec, JSValue value,
321                                              MessagePortArray* messagePorts, ArrayBufferArray* arrayBuffers,
322                                              Vector<String>& blobURLs, Vector<uint8_t>& out)
323     {
324         CloneSerializer serializer(exec, messagePorts, arrayBuffers, blobURLs, out);
325         return serializer.serialize(value);
326     }
327
328     static bool serialize(const String& s, Vector<uint8_t>& out)
329     {
330         writeLittleEndian(out, CurrentVersion);
331         if (s.isEmpty()) {
332             writeLittleEndian<uint8_t>(out, EmptyStringTag);
333             return true;
334         }
335         writeLittleEndian<uint8_t>(out, StringTag);
336         writeLittleEndian(out, s.length());
337         return writeLittleEndian(out, s.impl()->characters(), s.length());
338     }
339
340     static void serializeUndefined(Vector<uint8_t>& out)
341     {
342         writeLittleEndian(out, CurrentVersion);
343         writeLittleEndian<uint8_t>(out, UndefinedTag);
344     }
345
346     static void serializeBoolean(bool value, Vector<uint8_t>& out)
347     {
348         writeLittleEndian(out, CurrentVersion);
349         writeLittleEndian<uint8_t>(out, value ? TrueTag : FalseTag);
350     }
351
352     static void serializeNumber(double value, Vector<uint8_t>& out)
353     {
354         writeLittleEndian(out, CurrentVersion);
355         writeLittleEndian<uint8_t>(out, DoubleTag);
356         union {
357             double d;
358             int64_t i;
359         } u;
360         u.d = value;
361         writeLittleEndian(out, u.i);
362     }
363
364 private:
365     typedef HashMap<JSObject*, uint32_t> ObjectPool;
366
367     CloneSerializer(ExecState* exec, MessagePortArray* messagePorts, ArrayBufferArray* arrayBuffers, Vector<String>& blobURLs, Vector<uint8_t>& out)
368         : CloneBase(exec)
369         , m_buffer(out)
370         , m_blobURLs(blobURLs)
371         , m_emptyIdentifier(exec, emptyString())
372     {
373         write(CurrentVersion);
374         fillTransferMap(messagePorts, m_transferredMessagePorts);
375         fillTransferMap(arrayBuffers, m_transferredArrayBuffers);
376     }
377
378     template <class T>
379     void fillTransferMap(Vector<RefPtr<T>, 1>* input, ObjectPool& result)
380     {
381         if (!input)
382             return;
383         JSDOMGlobalObject* globalObject = jsCast<JSDOMGlobalObject*>(m_exec->lexicalGlobalObject());
384         for (size_t i = 0; i < input->size(); i++) {
385             JSC::JSValue value = toJS(m_exec, globalObject, input->at(i).get());
386             JSC::JSObject* obj = value.getObject();
387             if (obj && !result.contains(obj))
388                 result.add(obj, i);
389         }
390     }
391
392     SerializationReturnCode serialize(JSValue in);
393
394     bool isArray(JSValue value)
395     {
396         if (!value.isObject())
397             return false;
398         JSObject* object = asObject(value);
399         return isJSArray(object) || object->inherits(JSArray::info());
400     }
401
402     bool checkForDuplicate(JSObject* object)
403     {
404         // Record object for graph reconstruction
405         ObjectPool::const_iterator found = m_objectPool.find(object);
406
407         // Handle duplicate references
408         if (found != m_objectPool.end()) {
409             write(ObjectReferenceTag);
410             ASSERT(static_cast<int32_t>(found->value) < m_objectPool.size());
411             writeObjectIndex(found->value);
412             return true;
413         }
414
415         return false;
416     }
417
418     void recordObject(JSObject* object)
419     {
420         m_objectPool.add(object, m_objectPool.size());
421         m_gcBuffer.append(object);
422     }
423
424     bool startObjectInternal(JSObject* object)
425     {
426         if (checkForDuplicate(object))
427             return false;
428         recordObject(object);
429         return true;
430     }
431
432     bool startObject(JSObject* object)
433     {
434         if (!startObjectInternal(object))
435             return false;
436         write(ObjectTag);
437         return true;
438     }
439
440     bool startArray(JSArray* array)
441     {
442         if (!startObjectInternal(array))
443             return false;
444
445         unsigned length = array->length();
446         write(ArrayTag);
447         write(length);
448         return true;
449     }
450
451     void endObject()
452     {
453         write(TerminatorTag);
454     }
455
456     JSValue getProperty(JSObject* object, const Identifier& propertyName)
457     {
458         PropertySlot slot(object);
459         if (object->methodTable()->getOwnPropertySlot(object, m_exec, propertyName, slot))
460             return slot.getValue(m_exec, propertyName);
461         return JSValue();
462     }
463
464     void dumpImmediate(JSValue value)
465     {
466         if (value.isNull())
467             write(NullTag);
468         else if (value.isUndefined())
469             write(UndefinedTag);
470         else if (value.isNumber()) {
471             if (value.isInt32()) {
472                 if (!value.asInt32())
473                     write(ZeroTag);
474                 else if (value.asInt32() == 1)
475                     write(OneTag);
476                 else {
477                     write(IntTag);
478                     write(static_cast<uint32_t>(value.asInt32()));
479                 }
480             } else {
481                 write(DoubleTag);
482                 write(value.asDouble());
483             }
484         } else if (value.isBoolean()) {
485             if (value.isTrue())
486                 write(TrueTag);
487             else
488                 write(FalseTag);
489         }
490     }
491
492     void dumpString(String str)
493     {
494         if (str.isEmpty())
495             write(EmptyStringTag);
496         else {
497             write(StringTag);
498             write(str);
499         }
500     }
501
502     void dumpStringObject(String str)
503     {
504         if (str.isEmpty())
505             write(EmptyStringObjectTag);
506         else {
507             write(StringObjectTag);
508             write(str);
509         }
510     }
511
512     bool dumpArrayBufferView(JSObject* obj, SerializationReturnCode& code)
513     {
514         write(ArrayBufferViewTag);
515         if (obj->inherits(JSDataView::info()))
516             write(DataViewTag);
517         else if (obj->inherits(JSUint8ClampedArray::info()))
518             write(Uint8ClampedArrayTag);
519         else if (obj->inherits(JSInt8Array::info()))
520             write(Int8ArrayTag);
521         else if (obj->inherits(JSUint8Array::info()))
522             write(Uint8ArrayTag);
523         else if (obj->inherits(JSInt16Array::info()))
524             write(Int16ArrayTag);
525         else if (obj->inherits(JSUint16Array::info()))
526             write(Uint16ArrayTag);
527         else if (obj->inherits(JSInt32Array::info()))
528             write(Int32ArrayTag);
529         else if (obj->inherits(JSUint32Array::info()))
530             write(Uint32ArrayTag);
531         else if (obj->inherits(JSFloat32Array::info()))
532             write(Float32ArrayTag);
533         else if (obj->inherits(JSFloat64Array::info()))
534             write(Float64ArrayTag);
535         else
536             return false;
537
538         RefPtr<ArrayBufferView> arrayBufferView = toArrayBufferView(obj);
539         write(static_cast<uint32_t>(arrayBufferView->byteOffset()));
540         write(static_cast<uint32_t>(arrayBufferView->byteLength()));
541         RefPtr<ArrayBuffer> arrayBuffer = arrayBufferView->buffer();
542         if (!arrayBuffer) {
543             code = ValidationError;
544             return true;
545         }
546         JSValue bufferObj = toJS(m_exec, jsCast<JSDOMGlobalObject*>(m_exec->lexicalGlobalObject()), arrayBuffer.get());
547         return dumpIfTerminal(bufferObj, code);
548     }
549
550     bool dumpIfTerminal(JSValue value, SerializationReturnCode& code)
551     {
552         if (!value.isCell()) {
553             dumpImmediate(value);
554             return true;
555         }
556
557         if (value.isString()) {
558             String str = asString(value)->value(m_exec);
559             dumpString(str);
560             return true;
561         }
562
563         if (value.isNumber()) {
564             write(DoubleTag);
565             write(value.asNumber());
566             return true;
567         }
568
569         if (value.isObject() && asObject(value)->inherits(DateInstance::info())) {
570             write(DateTag);
571             write(asDateInstance(value)->internalNumber());
572             return true;
573         }
574
575         if (isArray(value))
576             return false;
577
578         if (value.isObject()) {
579             JSObject* obj = asObject(value);
580             if (obj->inherits(BooleanObject::info())) {
581                 if (!startObjectInternal(obj)) // handle duplicates
582                     return true;
583                 write(asBooleanObject(value)->internalValue().toBoolean(m_exec) ? TrueObjectTag : FalseObjectTag);
584                 return true;
585             }
586             if (obj->inherits(StringObject::info())) {
587                 if (!startObjectInternal(obj)) // handle duplicates
588                     return true;
589                 String str = asString(asStringObject(value)->internalValue())->value(m_exec);
590                 dumpStringObject(str);
591                 return true;
592             }
593             if (obj->inherits(NumberObject::info())) {
594                 if (!startObjectInternal(obj)) // handle duplicates
595                     return true;
596                 write(NumberObjectTag);
597                 NumberObject* obj = static_cast<NumberObject*>(asObject(value));
598                 write(obj->internalValue().asNumber());
599                 return true;
600             }
601             if (obj->inherits(JSFile::info())) {
602                 write(FileTag);
603                 write(toFile(obj));
604                 return true;
605             }
606             if (obj->inherits(JSFileList::info())) {
607                 FileList* list = toFileList(obj);
608                 write(FileListTag);
609                 unsigned length = list->length();
610                 write(length);
611                 for (unsigned i = 0; i < length; i++)
612                     write(list->item(i));
613                 return true;
614             }
615             if (obj->inherits(JSBlob::info())) {
616                 write(BlobTag);
617                 Blob* blob = toBlob(obj);
618                 m_blobURLs.append(blob->url());
619                 write(blob->url());
620                 write(blob->type());
621                 write(blob->size());
622                 return true;
623             }
624             if (obj->inherits(JSImageData::info())) {
625                 ImageData* data = toImageData(obj);
626                 write(ImageDataTag);
627                 write(data->width());
628                 write(data->height());
629                 write(data->data()->length());
630                 write(data->data()->data(), data->data()->length());
631                 return true;
632             }
633             if (obj->inherits(RegExpObject::info())) {
634                 RegExpObject* regExp = asRegExpObject(obj);
635                 char flags[3];
636                 int flagCount = 0;
637                 if (regExp->regExp()->global())
638                     flags[flagCount++] = 'g';
639                 if (regExp->regExp()->ignoreCase())
640                     flags[flagCount++] = 'i';
641                 if (regExp->regExp()->multiline())
642                     flags[flagCount++] = 'm';
643                 write(RegExpTag);
644                 write(regExp->regExp()->pattern());
645                 write(String(flags, flagCount));
646                 return true;
647             }
648             if (obj->inherits(JSMessagePort::info())) {
649                 ObjectPool::iterator index = m_transferredMessagePorts.find(obj);
650                 if (index != m_transferredMessagePorts.end()) {
651                     write(MessagePortReferenceTag);
652                     write(index->value);
653                     return true;
654                 }
655                 // MessagePort object could not be found in transferred message ports
656                 code = ValidationError;
657                 return true;
658             }
659             if (obj->inherits(JSArrayBuffer::info())) {
660                 RefPtr<ArrayBuffer> arrayBuffer = toArrayBuffer(obj);
661                 if (arrayBuffer->isNeutered()) {
662                     code = ValidationError;
663                     return true;
664                 }
665                 ObjectPool::iterator index = m_transferredArrayBuffers.find(obj);
666                 if (index != m_transferredArrayBuffers.end()) {
667                     write(ArrayBufferTransferTag);
668                     write(index->value);
669                     return true;
670                 }
671                 if (!startObjectInternal(obj)) // handle duplicates
672                     return true;
673                 write(ArrayBufferTag);
674                 write(arrayBuffer->byteLength());
675                 write(static_cast<const uint8_t *>(arrayBuffer->data()), arrayBuffer->byteLength());
676                 return true;
677             }
678             if (obj->inherits(JSArrayBufferView::info())) {
679                 if (checkForDuplicate(obj))
680                     return true;
681                 bool success = dumpArrayBufferView(obj, code);
682                 recordObject(obj);
683                 return success;
684             }
685
686             return false;
687         }
688         // Any other types are expected to serialize as null.
689         write(NullTag);
690         return true;
691     }
692
693     void write(SerializationTag tag)
694     {
695         writeLittleEndian<uint8_t>(m_buffer, static_cast<uint8_t>(tag));
696     }
697
698     void write(ArrayBufferViewSubtag tag)
699     {
700         writeLittleEndian<uint8_t>(m_buffer, static_cast<uint8_t>(tag));
701     }
702
703     void write(uint8_t c)
704     {
705         writeLittleEndian(m_buffer, c);
706     }
707
708     void write(uint32_t i)
709     {
710         writeLittleEndian(m_buffer, i);
711     }
712
713     void write(double d)
714     {
715         union {
716             double d;
717             int64_t i;
718         } u;
719         u.d = d;
720         writeLittleEndian(m_buffer, u.i);
721     }
722
723     void write(int32_t i)
724     {
725         writeLittleEndian(m_buffer, i);
726     }
727
728     void write(unsigned long long i)
729     {
730         writeLittleEndian(m_buffer, i);
731     }
732     
733     void write(uint16_t ch)
734     {
735         writeLittleEndian(m_buffer, ch);
736     }
737
738     void writeStringIndex(unsigned i)
739     {
740         writeConstantPoolIndex(m_constantPool, i);
741     }
742     
743     void writeObjectIndex(unsigned i)
744     {
745         writeConstantPoolIndex(m_objectPool, i);
746     }
747
748     template <class T> void writeConstantPoolIndex(const T& constantPool, unsigned i)
749     {
750         ASSERT(static_cast<int32_t>(i) < constantPool.size());
751         if (constantPool.size() <= 0xFF)
752             write(static_cast<uint8_t>(i));
753         else if (constantPool.size() <= 0xFFFF)
754             write(static_cast<uint16_t>(i));
755         else
756             write(static_cast<uint32_t>(i));
757     }
758
759     void write(const Identifier& ident)
760     {
761         const String& str = ident.string();
762         StringConstantPool::AddResult addResult = m_constantPool.add(str.impl(), m_constantPool.size());
763         if (!addResult.isNewEntry) {
764             write(StringPoolTag);
765             writeStringIndex(addResult.iterator->value);
766             return;
767         }
768
769         // This condition is unlikely to happen as they would imply an ~8gb
770         // string but we should guard against it anyway
771         if (str.length() >= StringPoolTag) {
772             fail();
773             return;
774         }
775
776         // Guard against overflow
777         if (str.length() > (numeric_limits<uint32_t>::max() - sizeof(uint32_t)) / sizeof(UChar)) {
778             fail();
779             return;
780         }
781
782         writeLittleEndian<uint32_t>(m_buffer, str.length());
783         if (!writeLittleEndian<uint16_t>(m_buffer, reinterpret_cast<const uint16_t*>(str.characters()), str.length()))
784             fail();
785     }
786
787     void write(const String& str)
788     {
789         if (str.isNull())
790             write(m_emptyIdentifier);
791         else
792             write(Identifier(m_exec, str));
793     }
794
795     void write(const File* file)
796     {
797         m_blobURLs.append(file->url());
798         write(file->path());
799         write(file->url());
800         write(file->type());
801     }
802
803     void write(const uint8_t* data, unsigned length)
804     {
805         m_buffer.append(data, length);
806     }
807
808     Vector<uint8_t>& m_buffer;
809     Vector<String>& m_blobURLs;
810     ObjectPool m_objectPool;
811     ObjectPool m_transferredMessagePorts;
812     ObjectPool m_transferredArrayBuffers;
813     typedef HashMap<RefPtr<StringImpl>, uint32_t, IdentifierRepHash> StringConstantPool;
814     StringConstantPool m_constantPool;
815     Identifier m_emptyIdentifier;
816 };
817
818 SerializationReturnCode CloneSerializer::serialize(JSValue in)
819 {
820     Vector<uint32_t, 16> indexStack;
821     Vector<uint32_t, 16> lengthStack;
822     Vector<PropertyNameArray, 16> propertyStack;
823     Vector<JSObject*, 32> inputObjectStack;
824     Vector<WalkerState, 16> stateStack;
825     WalkerState state = StateUnknown;
826     JSValue inValue = in;
827     while (1) {
828         switch (state) {
829             arrayStartState:
830             case ArrayStartState: {
831                 ASSERT(isArray(inValue));
832                 if (inputObjectStack.size() > maximumFilterRecursion)
833                     return StackOverflowError;
834
835                 JSArray* inArray = asArray(inValue);
836                 unsigned length = inArray->length();
837                 if (!startArray(inArray))
838                     break;
839                 inputObjectStack.append(inArray);
840                 indexStack.append(0);
841                 lengthStack.append(length);
842                 // fallthrough
843             }
844             arrayStartVisitMember:
845             case ArrayStartVisitMember: {
846                 JSObject* array = inputObjectStack.last();
847                 uint32_t index = indexStack.last();
848                 if (index == lengthStack.last()) {
849                     indexStack.removeLast();
850                     lengthStack.removeLast();
851
852                     propertyStack.append(PropertyNameArray(m_exec));
853                     array->methodTable()->getOwnNonIndexPropertyNames(array, m_exec, propertyStack.last(), ExcludeDontEnumProperties);
854                     if (propertyStack.last().size()) {
855                         write(NonIndexPropertiesTag);
856                         indexStack.append(0);
857                         goto objectStartVisitMember;
858                     }
859                     propertyStack.removeLast();
860
861                     endObject();
862                     inputObjectStack.removeLast();
863                     break;
864                 }
865                 inValue = array->getDirectIndex(m_exec, index);
866                 if (!inValue) {
867                     indexStack.last()++;
868                     goto arrayStartVisitMember;
869                 }
870
871                 write(index);
872                 SerializationReturnCode terminalCode = SuccessfullyCompleted;
873                 if (dumpIfTerminal(inValue, terminalCode)) {
874                     if (terminalCode != SuccessfullyCompleted)
875                         return terminalCode;
876                     indexStack.last()++;
877                     goto arrayStartVisitMember;
878                 }
879                 stateStack.append(ArrayEndVisitMember);
880                 goto stateUnknown;
881             }
882             case ArrayEndVisitMember: {
883                 indexStack.last()++;
884                 goto arrayStartVisitMember;
885             }
886             objectStartState:
887             case ObjectStartState: {
888                 ASSERT(inValue.isObject());
889                 if (inputObjectStack.size() > maximumFilterRecursion)
890                     return StackOverflowError;
891                 JSObject* inObject = asObject(inValue);
892                 if (!startObject(inObject))
893                     break;
894                 // At this point, all supported objects other than Object
895                 // objects have been handled. If we reach this point and
896                 // the input is not an Object object then we should throw
897                 // a DataCloneError.
898                 if (inObject->classInfo() != JSFinalObject::info())
899                     return DataCloneError;
900                 inputObjectStack.append(inObject);
901                 indexStack.append(0);
902                 propertyStack.append(PropertyNameArray(m_exec));
903                 inObject->methodTable()->getOwnPropertyNames(inObject, m_exec, propertyStack.last(), ExcludeDontEnumProperties);
904                 // fallthrough
905             }
906             objectStartVisitMember:
907             case ObjectStartVisitMember: {
908                 JSObject* object = inputObjectStack.last();
909                 uint32_t index = indexStack.last();
910                 PropertyNameArray& properties = propertyStack.last();
911                 if (index == properties.size()) {
912                     endObject();
913                     inputObjectStack.removeLast();
914                     indexStack.removeLast();
915                     propertyStack.removeLast();
916                     break;
917                 }
918                 inValue = getProperty(object, properties[index]);
919                 if (shouldTerminate())
920                     return ExistingExceptionError;
921
922                 if (!inValue) {
923                     // Property was removed during serialisation
924                     indexStack.last()++;
925                     goto objectStartVisitMember;
926                 }
927                 write(properties[index]);
928
929                 if (shouldTerminate())
930                     return ExistingExceptionError;
931
932                 SerializationReturnCode terminalCode = SuccessfullyCompleted;
933                 if (!dumpIfTerminal(inValue, terminalCode)) {
934                     stateStack.append(ObjectEndVisitMember);
935                     goto stateUnknown;
936                 }
937                 if (terminalCode != SuccessfullyCompleted)
938                     return terminalCode;
939                 // fallthrough
940             }
941             case ObjectEndVisitMember: {
942                 if (shouldTerminate())
943                     return ExistingExceptionError;
944
945                 indexStack.last()++;
946                 goto objectStartVisitMember;
947             }
948             stateUnknown:
949             case StateUnknown: {
950                 SerializationReturnCode terminalCode = SuccessfullyCompleted;
951                 if (dumpIfTerminal(inValue, terminalCode)) {
952                     if (terminalCode != SuccessfullyCompleted)
953                         return terminalCode;
954                     break;
955                 }
956
957                 if (isArray(inValue))
958                     goto arrayStartState;
959                 goto objectStartState;
960             }
961         }
962         if (stateStack.isEmpty())
963             break;
964
965         state = stateStack.last();
966         stateStack.removeLast();
967     }
968     if (m_failed)
969         return UnspecifiedError;
970
971     return SuccessfullyCompleted;
972 }
973
974 typedef Vector<JSC::ArrayBufferContents> ArrayBufferContentsArray;
975
976 class CloneDeserializer : CloneBase {
977 public:
978     static String deserializeString(const Vector<uint8_t>& buffer)
979     {
980         const uint8_t* ptr = buffer.begin();
981         const uint8_t* end = buffer.end();
982         uint32_t version;
983         if (!readLittleEndian(ptr, end, version) || version > CurrentVersion)
984             return String();
985         uint8_t tag;
986         if (!readLittleEndian(ptr, end, tag) || tag != StringTag)
987             return String();
988         uint32_t length;
989         if (!readLittleEndian(ptr, end, length) || length >= StringPoolTag)
990             return String();
991         String str;
992         if (!readString(ptr, end, str, length))
993             return String();
994         return String(str.impl());
995     }
996
997     static DeserializationResult deserialize(ExecState* exec, JSGlobalObject* globalObject,
998                                              MessagePortArray* messagePorts, ArrayBufferContentsArray* arrayBufferContentsArray,
999                                              const Vector<uint8_t>& buffer)
1000     {
1001         if (!buffer.size())
1002             return make_pair(jsNull(), UnspecifiedError);
1003         CloneDeserializer deserializer(exec, globalObject, messagePorts, arrayBufferContentsArray, buffer);
1004         if (!deserializer.isValid())
1005             return make_pair(JSValue(), ValidationError);
1006         return deserializer.deserialize();
1007     }
1008
1009 private:
1010     struct CachedString {
1011         CachedString(const String& string)
1012             : m_string(string)
1013         {
1014         }
1015
1016         JSValue jsString(ExecState* exec)
1017         {
1018             if (!m_jsString)
1019                 m_jsString = JSC::jsString(exec, m_string);
1020             return m_jsString;
1021         }
1022         const String& string() { return m_string; }
1023
1024     private:
1025         String m_string;
1026         JSValue m_jsString;
1027     };
1028
1029     struct CachedStringRef {
1030         CachedStringRef()
1031             : m_base(0)
1032             , m_index(0)
1033         {
1034         }
1035         CachedStringRef(Vector<CachedString>* base, size_t index)
1036             : m_base(base)
1037             , m_index(index)
1038         {
1039         }
1040         
1041         CachedString* operator->() { ASSERT(m_base); return &m_base->at(m_index); }
1042         
1043     private:
1044         Vector<CachedString>* m_base;
1045         size_t m_index;
1046     };
1047
1048     CloneDeserializer(ExecState* exec, JSGlobalObject* globalObject, 
1049                       MessagePortArray* messagePorts, ArrayBufferContentsArray* arrayBufferContents,
1050                       const Vector<uint8_t>& buffer)
1051         : CloneBase(exec)
1052         , m_globalObject(globalObject)
1053         , m_isDOMGlobalObject(globalObject->inherits(JSDOMGlobalObject::info()))
1054         , m_ptr(buffer.data())
1055         , m_end(buffer.data() + buffer.size())
1056         , m_version(0xFFFFFFFF)
1057         , m_messagePorts(messagePorts)
1058         , m_arrayBufferContents(arrayBufferContents)
1059         , m_arrayBuffers(arrayBufferContents ? arrayBufferContents->size() : 0)
1060     {
1061         if (!read(m_version))
1062             m_version = 0xFFFFFFFF;
1063     }
1064
1065     DeserializationResult deserialize();
1066
1067     void throwValidationError()
1068     {
1069         m_exec->vm().throwException(m_exec, createTypeError(m_exec, "Unable to deserialize data."));
1070     }
1071
1072     bool isValid() const { return m_version <= CurrentVersion; }
1073
1074     template <typename T> bool readLittleEndian(T& value)
1075     {
1076         if (m_failed || !readLittleEndian(m_ptr, m_end, value)) {
1077             fail();
1078             return false;
1079         }
1080         return true;
1081     }
1082 #if ASSUME_LITTLE_ENDIAN
1083     template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
1084     {
1085         if (ptr > end - sizeof(value))
1086             return false;
1087
1088         if (sizeof(T) == 1)
1089             value = *ptr++;
1090         else {
1091             value = *reinterpret_cast<const T*>(ptr);
1092             ptr += sizeof(T);
1093         }
1094         return true;
1095     }
1096 #else
1097     template <typename T> static bool readLittleEndian(const uint8_t*& ptr, const uint8_t* end, T& value)
1098     {
1099         if (ptr > end - sizeof(value))
1100             return false;
1101
1102         if (sizeof(T) == 1)
1103             value = *ptr++;
1104         else {
1105             value = 0;
1106             for (unsigned i = 0; i < sizeof(T); i++)
1107                 value += ((T)*ptr++) << (i * 8);
1108         }
1109         return true;
1110     }
1111 #endif
1112
1113     bool read(uint32_t& i)
1114     {
1115         return readLittleEndian(i);
1116     }
1117
1118     bool read(int32_t& i)
1119     {
1120         return readLittleEndian(*reinterpret_cast<uint32_t*>(&i));
1121     }
1122
1123     bool read(uint16_t& i)
1124     {
1125         return readLittleEndian(i);
1126     }
1127
1128     bool read(uint8_t& i)
1129     {
1130         return readLittleEndian(i);
1131     }
1132
1133     bool read(double& d)
1134     {
1135         union {
1136             double d;
1137             uint64_t i64;
1138         } u;
1139         if (!readLittleEndian(u.i64))
1140             return false;
1141         d = u.d;
1142         return true;
1143     }
1144
1145     bool read(unsigned long long& i)
1146     {
1147         return readLittleEndian(i);
1148     }
1149
1150     bool readStringIndex(uint32_t& i)
1151     {
1152         return readConstantPoolIndex(m_constantPool, i);
1153     }
1154
1155     template <class T> bool readConstantPoolIndex(const T& constantPool, uint32_t& i)
1156     {
1157         if (constantPool.size() <= 0xFF) {
1158             uint8_t i8;
1159             if (!read(i8))
1160                 return false;
1161             i = i8;
1162             return true;
1163         }
1164         if (constantPool.size() <= 0xFFFF) {
1165             uint16_t i16;
1166             if (!read(i16))
1167                 return false;
1168             i = i16;
1169             return true;
1170         }
1171         return read(i);
1172     }
1173
1174     static bool readString(const uint8_t*& ptr, const uint8_t* end, String& str, unsigned length)
1175     {
1176         if (length >= numeric_limits<int32_t>::max() / sizeof(UChar))
1177             return false;
1178
1179         unsigned size = length * sizeof(UChar);
1180         if ((end - ptr) < static_cast<int>(size))
1181             return false;
1182
1183 #if ASSUME_LITTLE_ENDIAN
1184         str = String(reinterpret_cast<const UChar*>(ptr), length);
1185         ptr += length * sizeof(UChar);
1186 #else
1187         Vector<UChar> buffer;
1188         buffer.reserveCapacity(length);
1189         for (unsigned i = 0; i < length; i++) {
1190             uint16_t ch;
1191             readLittleEndian(ptr, end, ch);
1192             buffer.append(ch);
1193         }
1194         str = String::adopt(buffer);
1195 #endif
1196         return true;
1197     }
1198
1199     bool readStringData(CachedStringRef& cachedString)
1200     {
1201         bool scratch;
1202         return readStringData(cachedString, scratch);
1203     }
1204
1205     bool readStringData(CachedStringRef& cachedString, bool& wasTerminator)
1206     {
1207         if (m_failed)
1208             return false;
1209         uint32_t length = 0;
1210         if (!read(length))
1211             return false;
1212         if (length == TerminatorTag) {
1213             wasTerminator = true;
1214             return false;
1215         }
1216         if (length == StringPoolTag) {
1217             unsigned index = 0;
1218             if (!readStringIndex(index)) {
1219                 fail();
1220                 return false;
1221             }
1222             if (index >= m_constantPool.size()) {
1223                 fail();
1224                 return false;
1225             }
1226             cachedString = CachedStringRef(&m_constantPool, index);
1227             return true;
1228         }
1229         String str;
1230         if (!readString(m_ptr, m_end, str, length)) {
1231             fail();
1232             return false;
1233         }
1234         m_constantPool.append(str);
1235         cachedString = CachedStringRef(&m_constantPool, m_constantPool.size() - 1);
1236         return true;
1237     }
1238
1239     SerializationTag readTag()
1240     {
1241         if (m_ptr >= m_end)
1242             return ErrorTag;
1243         return static_cast<SerializationTag>(*m_ptr++);
1244     }
1245
1246     bool readArrayBufferViewSubtag(ArrayBufferViewSubtag& tag)
1247     {
1248         if (m_ptr >= m_end)
1249             return false;
1250         tag = static_cast<ArrayBufferViewSubtag>(*m_ptr++);
1251         return true;
1252     }
1253
1254     void putProperty(JSObject* object, unsigned index, JSValue value)
1255     {
1256         object->putDirectIndex(m_exec, index, value);
1257     }
1258
1259     void putProperty(JSObject* object, const Identifier& property, JSValue value)
1260     {
1261         object->putDirectMayBeIndex(m_exec, property, value);
1262     }
1263
1264     bool readFile(RefPtr<File>& file)
1265     {
1266         CachedStringRef path;
1267         if (!readStringData(path))
1268             return 0;
1269         CachedStringRef url;
1270         if (!readStringData(url))
1271             return 0;
1272         CachedStringRef type;
1273         if (!readStringData(type))
1274             return 0;
1275         if (m_isDOMGlobalObject)
1276             file = File::create(path->string(), KURL(KURL(), url->string()), type->string());
1277         return true;
1278     }
1279
1280     bool readArrayBuffer(RefPtr<ArrayBuffer>& arrayBuffer)
1281     {
1282         uint32_t length;
1283         if (!read(length))
1284             return false;
1285         if (m_ptr + length > m_end)
1286             return false;
1287         arrayBuffer = ArrayBuffer::create(m_ptr, length);
1288         m_ptr += length;
1289         return true;
1290     }
1291
1292     bool readArrayBufferView(JSValue& arrayBufferView)
1293     {
1294         ArrayBufferViewSubtag arrayBufferViewSubtag;
1295         if (!readArrayBufferViewSubtag(arrayBufferViewSubtag))
1296             return false;
1297         uint32_t byteOffset;
1298         if (!read(byteOffset))
1299             return false;
1300         uint32_t byteLength;
1301         if (!read(byteLength))
1302             return false;
1303         JSObject* arrayBufferObj = asObject(readTerminal());
1304         if (!arrayBufferObj || !arrayBufferObj->inherits(JSArrayBuffer::info()))
1305             return false;
1306
1307         unsigned elementSize = typedArrayElementSize(arrayBufferViewSubtag);
1308         if (!elementSize)
1309             return false;
1310         unsigned length = byteLength / elementSize;
1311         if (length * elementSize != byteLength)
1312             return false;
1313
1314         RefPtr<ArrayBuffer> arrayBuffer = toArrayBuffer(arrayBufferObj);
1315         switch (arrayBufferViewSubtag) {
1316         case DataViewTag:
1317             arrayBufferView = getJSValue(DataView::create(arrayBuffer, byteOffset, length).get());
1318             return true;
1319         case Int8ArrayTag:
1320             arrayBufferView = getJSValue(Int8Array::create(arrayBuffer, byteOffset, length).get());
1321             return true;
1322         case Uint8ArrayTag:
1323             arrayBufferView = getJSValue(Uint8Array::create(arrayBuffer, byteOffset, length).get());
1324             return true;
1325         case Uint8ClampedArrayTag:
1326             arrayBufferView = getJSValue(Uint8ClampedArray::create(arrayBuffer, byteOffset, length).get());
1327             return true;
1328         case Int16ArrayTag:
1329             arrayBufferView = getJSValue(Int16Array::create(arrayBuffer, byteOffset, length).get());
1330             return true;
1331         case Uint16ArrayTag:
1332             arrayBufferView = getJSValue(Uint16Array::create(arrayBuffer, byteOffset, length).get());
1333             return true;
1334         case Int32ArrayTag:
1335             arrayBufferView = getJSValue(Int32Array::create(arrayBuffer, byteOffset, length).get());
1336             return true;
1337         case Uint32ArrayTag:
1338             arrayBufferView = getJSValue(Uint32Array::create(arrayBuffer, byteOffset, length).get());
1339             return true;
1340         case Float32ArrayTag:
1341             arrayBufferView = getJSValue(Float32Array::create(arrayBuffer, byteOffset, length).get());
1342             return true;
1343         case Float64ArrayTag:
1344             arrayBufferView = getJSValue(Float64Array::create(arrayBuffer, byteOffset, length).get());
1345             return true;
1346         default:
1347             return false;
1348         }
1349     }
1350
1351     template<class T>
1352     JSValue getJSValue(T* nativeObj)
1353     {
1354         return toJS(m_exec, jsCast<JSDOMGlobalObject*>(m_globalObject), nativeObj);
1355     }
1356
1357     JSValue readTerminal()
1358     {
1359         SerializationTag tag = readTag();
1360         switch (tag) {
1361         case UndefinedTag:
1362             return jsUndefined();
1363         case NullTag:
1364             return jsNull();
1365         case IntTag: {
1366             int32_t i;
1367             if (!read(i))
1368                 return JSValue();
1369             return jsNumber(i);
1370         }
1371         case ZeroTag:
1372             return jsNumber(0);
1373         case OneTag:
1374             return jsNumber(1);
1375         case FalseTag:
1376             return jsBoolean(false);
1377         case TrueTag:
1378             return jsBoolean(true);
1379         case FalseObjectTag: {
1380             BooleanObject* obj = BooleanObject::create(m_exec->vm(), m_globalObject->booleanObjectStructure());
1381             obj->setInternalValue(m_exec->vm(), jsBoolean(false));
1382             m_gcBuffer.append(obj);
1383             return obj;
1384         }
1385         case TrueObjectTag: {
1386             BooleanObject* obj = BooleanObject::create(m_exec->vm(), m_globalObject->booleanObjectStructure());
1387             obj->setInternalValue(m_exec->vm(), jsBoolean(true));
1388              m_gcBuffer.append(obj);
1389             return obj;
1390         }
1391         case DoubleTag: {
1392             double d;
1393             if (!read(d))
1394                 return JSValue();
1395             return jsNumber(d);
1396         }
1397         case NumberObjectTag: {
1398             double d;
1399             if (!read(d))
1400                 return JSValue();
1401             NumberObject* obj = constructNumber(m_exec, m_globalObject, jsNumber(d));
1402             m_gcBuffer.append(obj);
1403             return obj;
1404         }
1405         case DateTag: {
1406             double d;
1407             if (!read(d))
1408                 return JSValue();
1409             return DateInstance::create(m_exec, m_globalObject->dateStructure(), d);
1410         }
1411         case FileTag: {
1412             RefPtr<File> file;
1413             if (!readFile(file))
1414                 return JSValue();
1415             if (!m_isDOMGlobalObject)
1416                 return jsNull();
1417             return toJS(m_exec, jsCast<JSDOMGlobalObject*>(m_globalObject), file.get());
1418         }
1419         case FileListTag: {
1420             unsigned length = 0;
1421             if (!read(length))
1422                 return JSValue();
1423             RefPtr<FileList> result = FileList::create();
1424             for (unsigned i = 0; i < length; i++) {
1425                 RefPtr<File> file;
1426                 if (!readFile(file))
1427                     return JSValue();
1428                 if (m_isDOMGlobalObject)
1429                     result->append(file.get());
1430             }
1431             if (!m_isDOMGlobalObject)
1432                 return jsNull();
1433             return getJSValue(result.get());
1434         }
1435         case ImageDataTag: {
1436             int32_t width;
1437             if (!read(width))
1438                 return JSValue();
1439             int32_t height;
1440             if (!read(height))
1441                 return JSValue();
1442             uint32_t length;
1443             if (!read(length))
1444                 return JSValue();
1445             if (m_end < ((uint8_t*)0) + length || m_ptr > m_end - length) {
1446                 fail();
1447                 return JSValue();
1448             }
1449             if (!m_isDOMGlobalObject) {
1450                 m_ptr += length;
1451                 return jsNull();
1452             }
1453             RefPtr<ImageData> result = ImageData::create(IntSize(width, height));
1454             memcpy(result->data()->data(), m_ptr, length);
1455             m_ptr += length;
1456             return getJSValue(result.get());
1457         }
1458         case BlobTag: {
1459             CachedStringRef url;
1460             if (!readStringData(url))
1461                 return JSValue();
1462             CachedStringRef type;
1463             if (!readStringData(type))
1464                 return JSValue();
1465             unsigned long long size = 0;
1466             if (!read(size))
1467                 return JSValue();
1468             if (!m_isDOMGlobalObject)
1469                 return jsNull();
1470             return getJSValue(Blob::create(KURL(KURL(), url->string()), type->string(), size).get());
1471         }
1472         case StringTag: {
1473             CachedStringRef cachedString;
1474             if (!readStringData(cachedString))
1475                 return JSValue();
1476             return cachedString->jsString(m_exec);
1477         }
1478         case EmptyStringTag:
1479             return jsEmptyString(&m_exec->vm());
1480         case StringObjectTag: {
1481             CachedStringRef cachedString;
1482             if (!readStringData(cachedString))
1483                 return JSValue();
1484             StringObject* obj = constructString(m_exec, m_globalObject, cachedString->jsString(m_exec));
1485             m_gcBuffer.append(obj);
1486             return obj;
1487         }
1488         case EmptyStringObjectTag: {
1489             StringObject* obj = constructString(m_exec, m_globalObject, jsEmptyString(&m_exec->vm()));
1490             m_gcBuffer.append(obj);
1491             return obj;
1492         }
1493         case RegExpTag: {
1494             CachedStringRef pattern;
1495             if (!readStringData(pattern))
1496                 return JSValue();
1497             CachedStringRef flags;
1498             if (!readStringData(flags))
1499                 return JSValue();
1500             RegExpFlags reFlags = regExpFlags(flags->string());
1501             ASSERT(reFlags != InvalidFlags);
1502             RegExp* regExp = RegExp::create(m_exec->vm(), pattern->string(), reFlags);
1503             return RegExpObject::create(m_exec, m_exec->lexicalGlobalObject(), m_globalObject->regExpStructure(), regExp); 
1504         }
1505         case ObjectReferenceTag: {
1506             unsigned index = 0;
1507             if (!readConstantPoolIndex(m_gcBuffer, index)) {
1508                 fail();
1509                 return JSValue();
1510             }
1511             return m_gcBuffer.at(index);
1512         }
1513         case MessagePortReferenceTag: {
1514             uint32_t index;
1515             bool indexSuccessfullyRead = read(index);
1516             if (!indexSuccessfullyRead || !m_messagePorts || index >= m_messagePorts->size()) {
1517                 fail();
1518                 return JSValue();
1519             }
1520             return getJSValue(m_messagePorts->at(index).get());
1521         }
1522         case ArrayBufferTag: {
1523             RefPtr<ArrayBuffer> arrayBuffer;
1524             if (!readArrayBuffer(arrayBuffer)) {
1525                 fail();
1526                 return JSValue();
1527             }
1528             JSValue result = getJSValue(arrayBuffer.get());
1529             m_gcBuffer.append(result);
1530             return result;
1531         }
1532         case ArrayBufferTransferTag: {
1533             uint32_t index;
1534             bool indexSuccessfullyRead = read(index);
1535             if (!indexSuccessfullyRead || index >= m_arrayBuffers.size()) {
1536                 fail();
1537                 return JSValue();
1538             }
1539
1540             if (!m_arrayBuffers[index])
1541                 m_arrayBuffers[index] = ArrayBuffer::create(m_arrayBufferContents->at(index));
1542
1543             return getJSValue(m_arrayBuffers[index].get());
1544         }
1545         case ArrayBufferViewTag: {
1546             JSValue arrayBufferView;
1547             if (!readArrayBufferView(arrayBufferView)) {
1548                 fail();
1549                 return JSValue();
1550             }
1551             m_gcBuffer.append(arrayBufferView);
1552             return arrayBufferView;
1553         }
1554         default:
1555             m_ptr--; // Push the tag back
1556             return JSValue();
1557         }
1558     }
1559
1560     JSGlobalObject* m_globalObject;
1561     bool m_isDOMGlobalObject;
1562     const uint8_t* m_ptr;
1563     const uint8_t* m_end;
1564     unsigned m_version;
1565     Vector<CachedString> m_constantPool;
1566     MessagePortArray* m_messagePorts;
1567     ArrayBufferContentsArray* m_arrayBufferContents;
1568     ArrayBufferArray m_arrayBuffers;
1569 };
1570
1571 DeserializationResult CloneDeserializer::deserialize()
1572 {
1573     Vector<uint32_t, 16> indexStack;
1574     Vector<Identifier, 16> propertyNameStack;
1575     Vector<JSObject*, 32> outputObjectStack;
1576     Vector<WalkerState, 16> stateStack;
1577     WalkerState state = StateUnknown;
1578     JSValue outValue;
1579
1580     while (1) {
1581         switch (state) {
1582         arrayStartState:
1583         case ArrayStartState: {
1584             uint32_t length;
1585             if (!read(length)) {
1586                 fail();
1587                 goto error;
1588             }
1589             JSArray* outArray = constructEmptyArray(m_exec, 0, m_globalObject, length);
1590             m_gcBuffer.append(outArray);
1591             outputObjectStack.append(outArray);
1592             // fallthrough
1593         }
1594         arrayStartVisitMember:
1595         case ArrayStartVisitMember: {
1596             uint32_t index;
1597             if (!read(index)) {
1598                 fail();
1599                 goto error;
1600             }
1601             if (index == TerminatorTag) {
1602                 JSObject* outArray = outputObjectStack.last();
1603                 outValue = outArray;
1604                 outputObjectStack.removeLast();
1605                 break;
1606             } else if (index == NonIndexPropertiesTag) {
1607                 goto objectStartVisitMember;
1608             }
1609
1610             if (JSValue terminal = readTerminal()) {
1611                 putProperty(outputObjectStack.last(), index, terminal);
1612                 goto arrayStartVisitMember;
1613             }
1614             if (m_failed)
1615                 goto error;
1616             indexStack.append(index);
1617             stateStack.append(ArrayEndVisitMember);
1618             goto stateUnknown;
1619         }
1620         case ArrayEndVisitMember: {
1621             JSObject* outArray = outputObjectStack.last();
1622             putProperty(outArray, indexStack.last(), outValue);
1623             indexStack.removeLast();
1624             goto arrayStartVisitMember;
1625         }
1626         objectStartState:
1627         case ObjectStartState: {
1628             if (outputObjectStack.size() > maximumFilterRecursion)
1629                 return make_pair(JSValue(), StackOverflowError);
1630             JSObject* outObject = constructEmptyObject(m_exec, m_globalObject->objectPrototype());
1631             m_gcBuffer.append(outObject);
1632             outputObjectStack.append(outObject);
1633             // fallthrough
1634         }
1635         objectStartVisitMember:
1636         case ObjectStartVisitMember: {
1637             CachedStringRef cachedString;
1638             bool wasTerminator = false;
1639             if (!readStringData(cachedString, wasTerminator)) {
1640                 if (!wasTerminator)
1641                     goto error;
1642
1643                 JSObject* outObject = outputObjectStack.last();
1644                 outValue = outObject;
1645                 outputObjectStack.removeLast();
1646                 break;
1647             }
1648
1649             if (JSValue terminal = readTerminal()) {
1650                 putProperty(outputObjectStack.last(), Identifier(m_exec, cachedString->string()), terminal);
1651                 goto objectStartVisitMember;
1652             }
1653             stateStack.append(ObjectEndVisitMember);
1654             propertyNameStack.append(Identifier(m_exec, cachedString->string()));
1655             goto stateUnknown;
1656         }
1657         case ObjectEndVisitMember: {
1658             putProperty(outputObjectStack.last(), propertyNameStack.last(), outValue);
1659             propertyNameStack.removeLast();
1660             goto objectStartVisitMember;
1661         }
1662         stateUnknown:
1663         case StateUnknown:
1664             if (JSValue terminal = readTerminal()) {
1665                 outValue = terminal;
1666                 break;
1667             }
1668             SerializationTag tag = readTag();
1669             if (tag == ArrayTag)
1670                 goto arrayStartState;
1671             if (tag == ObjectTag)
1672                 goto objectStartState;
1673             goto error;
1674         }
1675         if (stateStack.isEmpty())
1676             break;
1677
1678         state = stateStack.last();
1679         stateStack.removeLast();
1680     }
1681     ASSERT(outValue);
1682     ASSERT(!m_failed);
1683     return make_pair(outValue, SuccessfullyCompleted);
1684 error:
1685     fail();
1686     return make_pair(JSValue(), ValidationError);
1687 }
1688
1689
1690
1691 SerializedScriptValue::~SerializedScriptValue()
1692 {
1693 }
1694
1695 SerializedScriptValue::SerializedScriptValue(const Vector<uint8_t>& buffer)
1696     : m_data(buffer)
1697 {
1698 }
1699
1700 SerializedScriptValue::SerializedScriptValue(Vector<uint8_t>& buffer)
1701 {
1702     m_data.swap(buffer);
1703 }
1704
1705 SerializedScriptValue::SerializedScriptValue(Vector<uint8_t>& buffer, Vector<String>& blobURLs)
1706 {
1707     m_data.swap(buffer);
1708     m_blobURLs.swap(blobURLs);
1709 }
1710
1711 SerializedScriptValue::SerializedScriptValue(Vector<uint8_t>& buffer, Vector<String>& blobURLs, PassOwnPtr<ArrayBufferContentsArray> arrayBufferContentsArray)
1712     : m_arrayBufferContentsArray(arrayBufferContentsArray)
1713 {
1714     m_data.swap(buffer);
1715     m_blobURLs.swap(blobURLs);
1716 }
1717
1718 PassOwnPtr<SerializedScriptValue::ArrayBufferContentsArray> SerializedScriptValue::transferArrayBuffers(
1719     ExecState* exec, ArrayBufferArray& arrayBuffers, SerializationReturnCode& code)
1720 {
1721     for (size_t i = 0; i < arrayBuffers.size(); i++) {
1722         if (arrayBuffers[i]->isNeutered()) {
1723             code = ValidationError;
1724             return nullptr;
1725         }
1726     }
1727
1728     OwnPtr<ArrayBufferContentsArray> contents = adoptPtr(new ArrayBufferContentsArray(arrayBuffers.size()));
1729     Vector<RefPtr<DOMWrapperWorld> > worlds;
1730     static_cast<WebCoreJSClientData*>(exec->vm().clientData)->getAllWorlds(worlds);
1731
1732     HashSet<JSC::ArrayBuffer*> visited;
1733     for (size_t arrayBufferIndex = 0; arrayBufferIndex < arrayBuffers.size(); arrayBufferIndex++) {
1734         if (visited.contains(arrayBuffers[arrayBufferIndex].get()))
1735             continue;
1736         visited.add(arrayBuffers[arrayBufferIndex].get());
1737
1738         bool result = arrayBuffers[arrayBufferIndex]->transfer(contents->at(arrayBufferIndex));
1739         if (!result) {
1740             code = ValidationError;
1741             return nullptr;
1742         }
1743     }
1744     return contents.release();
1745 }
1746
1747
1748 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(ExecState* exec, JSValue value,
1749                                                                 MessagePortArray* messagePorts, ArrayBufferArray* arrayBuffers,
1750                                                                 SerializationErrorMode throwExceptions)
1751 {
1752     Vector<uint8_t> buffer;
1753     Vector<String> blobURLs;
1754     SerializationReturnCode code = CloneSerializer::serialize(exec, value, messagePorts, arrayBuffers, blobURLs, buffer);
1755
1756     OwnPtr<ArrayBufferContentsArray> arrayBufferContentsArray;
1757
1758     if (arrayBuffers && serializationDidCompleteSuccessfully(code))
1759         arrayBufferContentsArray = transferArrayBuffers(exec, *arrayBuffers, code);
1760
1761     if (throwExceptions == Throwing)
1762         maybeThrowExceptionIfSerializationFailed(exec, code);
1763
1764     if (!serializationDidCompleteSuccessfully(code))
1765         return 0;
1766
1767     return adoptRef(new SerializedScriptValue(buffer, blobURLs, arrayBufferContentsArray.release()));
1768 }
1769
1770 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create()
1771 {
1772     Vector<uint8_t> buffer;
1773     return adoptRef(new SerializedScriptValue(buffer));
1774 }
1775
1776 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(const String& string)
1777 {
1778     Vector<uint8_t> buffer;
1779     if (!CloneSerializer::serialize(string, buffer))
1780         return 0;
1781     return adoptRef(new SerializedScriptValue(buffer));
1782 }
1783
1784 #if ENABLE(INDEXED_DATABASE)
1785 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(JSC::ExecState* exec, JSC::JSValue value)
1786 {
1787     return SerializedScriptValue::create(exec, value, 0, 0);
1788 }
1789
1790 PassRefPtr<SerializedScriptValue> SerializedScriptValue::numberValue(double value)
1791 {
1792     Vector<uint8_t> buffer;
1793     CloneSerializer::serializeNumber(value, buffer);
1794     return adoptRef(new SerializedScriptValue(buffer));
1795 }
1796
1797 JSValue SerializedScriptValue::deserialize(JSC::ExecState* exec, JSC::JSGlobalObject* globalObject)
1798 {
1799     return deserialize(exec, globalObject, 0);
1800 }
1801 #endif
1802
1803 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(JSContextRef originContext, JSValueRef apiValue, 
1804                                                                 MessagePortArray* messagePorts, ArrayBufferArray* arrayBuffers,
1805                                                                 JSValueRef* exception)
1806 {
1807     ExecState* exec = toJS(originContext);
1808     APIEntryShim entryShim(exec);
1809     JSValue value = toJS(exec, apiValue);
1810     RefPtr<SerializedScriptValue> serializedValue = SerializedScriptValue::create(exec, value, messagePorts, arrayBuffers);
1811     if (exec->hadException()) {
1812         if (exception)
1813             *exception = toRef(exec, exec->exception());
1814         exec->clearException();
1815         return 0;
1816     }
1817     ASSERT(serializedValue);
1818     return serializedValue.release();
1819 }
1820
1821 PassRefPtr<SerializedScriptValue> SerializedScriptValue::create(JSContextRef originContext, JSValueRef apiValue,
1822                                                                 JSValueRef* exception)
1823 {
1824     return create(originContext, apiValue, 0, 0, exception);
1825 }
1826
1827 String SerializedScriptValue::toString()
1828 {
1829     return CloneDeserializer::deserializeString(m_data);
1830 }
1831
1832 JSValue SerializedScriptValue::deserialize(ExecState* exec, JSGlobalObject* globalObject,
1833                                            MessagePortArray* messagePorts, SerializationErrorMode throwExceptions)
1834 {
1835     DeserializationResult result = CloneDeserializer::deserialize(exec, globalObject, messagePorts,
1836                                                                   m_arrayBufferContentsArray.get(), m_data);
1837     if (throwExceptions == Throwing)
1838         maybeThrowExceptionIfSerializationFailed(exec, result.second);
1839     return result.first;
1840 }
1841
1842 #if ENABLE(INSPECTOR)
1843 ScriptValue SerializedScriptValue::deserializeForInspector(ScriptState* scriptState)
1844 {
1845     JSValue value = deserialize(scriptState, scriptState->lexicalGlobalObject(), 0);
1846     return ScriptValue(scriptState->vm(), value);
1847 }
1848 #endif
1849
1850 JSValueRef SerializedScriptValue::deserialize(JSContextRef destinationContext, JSValueRef* exception, MessagePortArray* messagePorts)
1851 {
1852     ExecState* exec = toJS(destinationContext);
1853     APIEntryShim entryShim(exec);
1854     JSValue value = deserialize(exec, exec->lexicalGlobalObject(), messagePorts);
1855     if (exec->hadException()) {
1856         if (exception)
1857             *exception = toRef(exec, exec->exception());
1858         exec->clearException();
1859         return 0;
1860     }
1861     ASSERT(value);
1862     return toRef(exec, value);
1863 }
1864
1865
1866 JSValueRef SerializedScriptValue::deserialize(JSContextRef destinationContext, JSValueRef* exception)
1867 {
1868     return deserialize(destinationContext, exception, 0);
1869 }
1870
1871 PassRefPtr<SerializedScriptValue> SerializedScriptValue::nullValue()
1872 {
1873     return SerializedScriptValue::create();
1874 }
1875
1876 PassRefPtr<SerializedScriptValue> SerializedScriptValue::undefinedValue()
1877 {
1878     Vector<uint8_t> buffer;
1879     CloneSerializer::serializeUndefined(buffer);
1880     return adoptRef(new SerializedScriptValue(buffer));
1881 }
1882
1883 PassRefPtr<SerializedScriptValue> SerializedScriptValue::booleanValue(bool value)
1884 {
1885     Vector<uint8_t> buffer;
1886     CloneSerializer::serializeBoolean(value, buffer);
1887     return adoptRef(new SerializedScriptValue(buffer));
1888 }
1889
1890 void SerializedScriptValue::maybeThrowExceptionIfSerializationFailed(ExecState* exec, SerializationReturnCode code)
1891 {
1892     if (code == SuccessfullyCompleted)
1893         return;
1894     
1895     switch (code) {
1896     case StackOverflowError:
1897         exec->vm().throwException(exec, createStackOverflowError(exec));
1898         break;
1899     case ValidationError:
1900         exec->vm().throwException(exec, createTypeError(exec, "Unable to deserialize data."));
1901         break;
1902     case DataCloneError:
1903         setDOMException(exec, DATA_CLONE_ERR);
1904         break;
1905     case ExistingExceptionError:
1906         break;
1907     case UnspecifiedError:
1908         break;
1909     default:
1910         ASSERT_NOT_REACHED();
1911     }
1912 }
1913
1914 bool SerializedScriptValue::serializationDidCompleteSuccessfully(SerializationReturnCode code)
1915 {
1916     return (code == SuccessfullyCompleted);
1917 }
1918
1919 uint32_t SerializedScriptValue::wireFormatVersion()
1920 {
1921     return CurrentVersion;
1922 }
1923
1924 }