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