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