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<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<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 }