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