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