1 /* 2 * Copyright (C) 2010 Google 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 are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include "config.h" 32 #include "SerializedScriptValue.h" 33 34 #include "SharedBuffer.h" 35 36 #include <v8.h> 37 #include <wtf/Assertions.h> 38 #include <wtf/RefCounted.h> 39 #include <wtf/Vector.h> 40 41 // FIXME: 42 // - catch V8 exceptions 43 // - be ready to get empty handles 44 // - consider crashing in debug mode on deserialization errors 45 46 namespace WebCore { 47 48 namespace { 49 50 typedef UChar BufferValueType; 51 52 // Serialization format is a sequence of (tag, optional data) 53 // pairs. Tag always takes exactly one byte. 54 enum SerializationTag { 55 InvalidTag = '!', 56 PaddingTag = '\0', 57 UndefinedTag = '_', 58 NullTag = '0', 59 TrueTag = 'T', 60 FalseTag = 'F', 61 StringTag = 'S', 62 Int32Tag = 'I', 63 NumberTag = 'N', 64 ObjectTag = '{', 65 ArrayTag = '[', 66 }; 67 68 // Helpers to do verbose handle casts. 69 70 template <typename T, typename U> 71 static v8::Handle<T> handleCast(v8::Handle<U> handle) { return v8::Handle<T>::Cast(handle); } 72 73 template <typename T, typename U> 74 static v8::Local<T> handleCast(v8::Local<U> handle) { return v8::Local<T>::Cast(handle); } 75 76 static bool shouldCheckForCycles(int depth) 77 { 78 ASSERT(depth >= 0); 79 // Since we are not required to spot the cycle as soon as it 80 // happens we can check for cycles only when the current depth 81 // is a power of two. 82 return !(depth & (depth - 1)); 83 } 84 85 static const int maxDepth = 20000; 86 87 // VarInt encoding constants. 88 static const int varIntShift = 7; 89 static const int varIntMask = (1 << varIntShift) - 1; 90 91 // ZigZag encoding helps VarInt encoding stay small for negative 92 // numbers with small absolute values. 93 class ZigZag { 94 public: 95 static uint32_t encode(uint32_t value) 96 { 97 if (value & (1U << 31)) 98 value = ((~value) << 1) + 1; 99 else 100 value <<= 1; 101 return value; 102 } 103 104 static uint32_t decode(uint32_t value) 105 { 106 if (value & 1) 107 value = ~(value >> 1); 108 else 109 value >>= 1; 110 return value; 111 } 112 113 private: 114 ZigZag(); 115 }; 116 117 // Writer is responsible for serializing primitive types and storing 118 // information used to reconstruct composite types. 119 class Writer : Noncopyable { 120 public: 121 Writer() : m_position(0) 122 { 123 } 124 125 // Write functions for primitive types. 126 127 void writeUndefined() { append(UndefinedTag); } 128 129 void writeNull() { append(NullTag); } 130 131 void writeTrue() { append(TrueTag); } 132 133 void writeFalse() { append(FalseTag); } 134 135 void writeString(const char* data, int length) 136 { 137 append(StringTag); 138 doWriteUint32(static_cast<uint32_t>(length)); 139 append(data, length); 140 } 141 142 void writeInt32(int32_t value) 143 { 144 append(Int32Tag); 145 doWriteUint32(ZigZag::encode(static_cast<uint32_t>(value))); 146 } 147 148 void writeNumber(double number) 149 { 150 append(NumberTag); 151 append(reinterpret_cast<char*>(&number), sizeof(number)); 152 } 153 154 // Records that a composite object can be constructed by using 155 // |length| previously stored values. 156 void endComposite(SerializationTag tag, int32_t length) 157 { 158 ASSERT(tag == ObjectTag || tag == ArrayTag); 159 append(tag); 160 doWriteUint32(static_cast<uint32_t>(length)); 161 } 162 163 Vector<BufferValueType>& data() 164 { 165 fillHole(); 166 return m_buffer; 167 } 168 169 private: 170 void doWriteUint32(uint32_t value) 171 { 172 while (true) { 173 char b = (value & varIntMask); 174 value >>= varIntShift; 175 if (!value) { 176 append(b); 177 break; 178 } 179 append(b | (1 << varIntShift)); 180 } 181 } 182 183 void append(SerializationTag tag) 184 { 185 append(static_cast<char>(tag)); 186 } 187 188 void append(char b) 189 { 190 ensureSpace(1); 191 *charAt(m_position++) = b; 192 } 193 194 void append(const char* data, int length) 195 { 196 ensureSpace(length); 197 memcpy(charAt(m_position), data, length); 198 m_position += length; 199 } 200 201 void ensureSpace(int extra) 202 { 203 COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes); 204 m_buffer.grow((m_position + extra + 1) / 2); // "+ 1" to round up. 205 } 206 207 void fillHole() 208 { 209 COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes); 210 // If the writer is at odd position in the buffer, then one of 211 // the bytes in the last UChar is not initialized. 212 if (m_position % 2) 213 *charAt(m_position) = static_cast<char>(PaddingTag); 214 } 215 216 char* charAt(int position) { return reinterpret_cast<char*>(m_buffer.data()) + position; } 217 218 Vector<BufferValueType> m_buffer; 219 unsigned m_position; 220 }; 221 222 class Serializer { 223 public: 224 explicit Serializer(Writer& writer) 225 : m_writer(writer) 226 , m_state(0) 227 , m_depth(0) 228 { 229 } 230 231 bool serialize(v8::Handle<v8::Value> value) 232 { 233 v8::HandleScope scope; 234 StackCleaner cleaner(&m_state); 235 if (!doSerialize(value)) 236 return false; 237 while (top()) { 238 int length; 239 while (!top()->isDone(&length)) { 240 // Note that doSerialize() can change current top(). 241 if (!doSerialize(top()->advance())) 242 return false; 243 } 244 m_writer.endComposite(top()->tag(), length); 245 pop(); 246 } 247 return true; 248 } 249 250 private: 251 class StateBase : public Noncopyable { 252 public: 253 virtual ~StateBase() { } 254 255 // Link to the next state to form a stack. 256 StateBase* nextState() { return m_next; } 257 void setNextState(StateBase* next) { m_next = next; } 258 259 // Composite object we're processing in this state. 260 v8::Handle<v8::Value> composite() { return m_composite; } 261 262 // Serialization tag for the current composite. 263 virtual SerializationTag tag() const = 0; 264 265 // Returns whether iteration over subobjects of the current 266 // composite object is done. If yes, |*length| is set to the 267 // number of subobjects. 268 virtual bool isDone(int* length) = 0; 269 270 // Advances to the next subobject. 271 // Requires: !this->isDone(). 272 virtual v8::Local<v8::Value> advance() = 0; 273 274 protected: 275 StateBase(v8::Handle<v8::Value> composite) 276 : m_next(0) 277 , m_composite(composite) 278 { 279 } 280 281 private: 282 StateBase* m_next; 283 v8::Handle<v8::Value> m_composite; 284 }; 285 286 template <typename T, SerializationTag compositeTag> 287 class State : public StateBase { 288 public: 289 v8::Handle<T> composite() { return handleCast<T>(StateBase::composite()); } 290 291 virtual SerializationTag tag() const { return compositeTag; } 292 293 protected: 294 explicit State(v8::Handle<T> composite) : StateBase(composite) 295 { 296 } 297 }; 298 299 // Helper to clean up the state stack in case of errors. 300 class StackCleaner : Noncopyable { 301 public: 302 explicit StackCleaner(StateBase** stack) : m_stack(stack) 303 { 304 } 305 306 ~StackCleaner() 307 { 308 StateBase* state = *m_stack; 309 while (state) { 310 StateBase* tmp = state->nextState(); 311 delete state; 312 state = tmp; 313 } 314 *m_stack = 0; 315 } 316 317 private: 318 StateBase** m_stack; 319 }; 320 321 class ArrayState : public State<v8::Array, ArrayTag> { 322 public: 323 ArrayState(v8::Handle<v8::Array> array) 324 : State<v8::Array, ArrayTag>(array) 325 , m_index(0) 326 { 327 } 328 329 virtual bool isDone(int* length) 330 { 331 *length = composite()->Length(); 332 return static_cast<int>(m_index) >= *length; 333 } 334 335 virtual v8::Local<v8::Value> advance() 336 { 337 ASSERT(m_index < composite()->Length()); 338 v8::HandleScope scope; 339 return scope.Close(composite()->Get(v8::Integer::New(m_index++))); 340 } 341 342 private: 343 unsigned m_index; 344 }; 345 346 class ObjectState : public State<v8::Object, ObjectTag> { 347 public: 348 ObjectState(v8::Handle<v8::Object> object) 349 : State<v8::Object, ObjectTag>(object) 350 , m_propertyNames(object->GetPropertyNames()) 351 , m_index(-1) 352 , m_length(0) 353 { 354 nextProperty(); 355 } 356 357 virtual bool isDone(int* length) 358 { 359 *length = m_length; 360 return m_index >= 2 * m_propertyNames->Length(); 361 } 362 363 virtual v8::Local<v8::Value> advance() 364 { 365 ASSERT(m_index < 2 * m_propertyNames->Length()); 366 if (!(m_index % 2)) { 367 ++m_index; 368 return m_propertyName; 369 } 370 v8::Local<v8::Value> result = composite()->Get(m_propertyName); 371 nextProperty(); 372 return result; 373 } 374 375 private: 376 void nextProperty() 377 { 378 v8::HandleScope scope; 379 ++m_index; 380 ASSERT(!(m_index % 2)); 381 for (; m_index < 2 * m_propertyNames->Length(); m_index += 2) { 382 v8::Local<v8::Value> propertyName = m_propertyNames->Get(v8::Integer::New(m_index / 2)); 383 if ((propertyName->IsString() && composite()->HasRealNamedProperty(handleCast<v8::String>(propertyName))) 384 || (propertyName->IsInt32() && composite()->HasRealIndexedProperty(propertyName->Uint32Value()))) { 385 m_propertyName = scope.Close(propertyName); 386 m_length += 2; 387 return; 388 } 389 } 390 } 391 392 v8::Local<v8::Array> m_propertyNames; 393 v8::Local<v8::Value> m_propertyName; 394 unsigned m_index; 395 unsigned m_length; 396 }; 397 398 bool doSerialize(v8::Handle<v8::Value> value) 399 { 400 if (value->IsUndefined()) 401 m_writer.writeUndefined(); 402 else if (value->IsNull()) 403 m_writer.writeNull(); 404 else if (value->IsTrue()) 405 m_writer.writeTrue(); 406 else if (value->IsFalse()) 407 m_writer.writeFalse(); 408 else if (value->IsInt32()) 409 m_writer.writeInt32(value->Int32Value()); 410 else if (value->IsNumber()) 411 m_writer.writeNumber(handleCast<v8::Number>(value)->Value()); 412 else if (value->IsString()) { 413 v8::String::Utf8Value stringValue(value); 414 m_writer.writeString(*stringValue, stringValue.length()); 415 } else if (value->IsArray()) { 416 if (!checkComposite(value)) 417 return false; 418 push(new ArrayState(handleCast<v8::Array>(value))); 419 } else if (value->IsObject()) { 420 if (!checkComposite(value)) 421 return false; 422 push(new ObjectState(handleCast<v8::Object>(value))); 423 // FIXME: 424 // - check not a wrapper 425 // - support File, ImageData, etc. 426 } 427 return true; 428 } 429 430 void push(StateBase* state) 431 { 432 state->setNextState(m_state); 433 m_state = state; 434 ++m_depth; 435 } 436 437 StateBase* top() { return m_state; } 438 439 void pop() 440 { 441 if (!m_state) 442 return; 443 StateBase* top = m_state; 444 m_state = top->nextState(); 445 delete top; 446 --m_depth; 447 } 448 449 bool checkComposite(v8::Handle<v8::Value> composite) 450 { 451 if (m_depth > maxDepth) 452 return false; 453 if (!shouldCheckForCycles(m_depth)) 454 return true; 455 for (StateBase* state = top(); state; state = state->nextState()) { 456 if (state->composite() == composite) 457 return false; 458 } 459 return true; 460 } 461 462 Writer& m_writer; 463 StateBase* m_state; 464 int m_depth; 465 }; 466 467 // Reader is responsible for deserializing primitive types and 468 // restoring information about saved objects of composite types. 469 class Reader { 470 public: 471 Reader(const char* buffer, int length) 472 : m_buffer(buffer) 473 , m_length(length) 474 , m_position(0) 475 { 476 ASSERT(length >= 0); 477 } 478 479 bool isEof() const { return m_position >= m_length; } 480 481 bool read(SerializationTag* tag, v8::Handle<v8::Value>* value, int* length) 482 { 483 uint32_t rawLength; 484 if (!readTag(tag)) 485 return false; 486 switch (*tag) { 487 case InvalidTag: 488 return false; 489 case PaddingTag: 490 break; 491 case UndefinedTag: 492 *value = v8::Undefined(); 493 break; 494 case NullTag: 495 *value = v8::Null(); 496 break; 497 case TrueTag: 498 *value = v8::True(); 499 break; 500 case FalseTag: 501 *value = v8::False(); 502 break; 503 case StringTag: 504 if (!readString(value)) 505 return false; 506 break; 507 case Int32Tag: 508 if (!readInt32(value)) 509 return false; 510 break; 511 case NumberTag: 512 if (!readNumber(value)) 513 return false; 514 break; 515 case ObjectTag: 516 case ArrayTag: 517 if (!doReadUint32(&rawLength)) 518 return false; 519 *length = rawLength; 520 break; 521 } 522 return true; 523 } 524 525 private: 526 bool readTag(SerializationTag* tag) 527 { 528 if (m_position >= m_length) 529 return false; 530 *tag = static_cast<SerializationTag>(m_buffer[m_position++]); 531 return true; 532 } 533 534 bool readString(v8::Handle<v8::Value>* value) 535 { 536 uint32_t length; 537 if (!doReadUint32(&length)) 538 return false; 539 if (m_position + length > m_length) 540 return false; 541 *value = v8::String::New(m_buffer + m_position, length); 542 m_position += length; 543 return true; 544 } 545 546 bool readInt32(v8::Handle<v8::Value>* value) 547 { 548 uint32_t rawValue; 549 if (!doReadUint32(&rawValue)) 550 return false; 551 *value = v8::Integer::New(static_cast<int32_t>(ZigZag::decode(rawValue))); 552 return true; 553 } 554 555 bool readNumber(v8::Handle<v8::Value>* value) 556 { 557 if (m_position + sizeof(double) > m_length) 558 return false; 559 double number; 560 char* numberAsByteArray = reinterpret_cast<char*>(&number); 561 for (unsigned i = 0; i < sizeof(double); ++i) 562 numberAsByteArray[i] = m_buffer[m_position++]; 563 *value = v8::Number::New(number); 564 return true; 565 } 566 567 bool doReadUint32(uint32_t* value) 568 { 569 *value = 0; 570 char currentByte; 571 int shift = 0; 572 do { 573 if (m_position >= m_length) 574 return false; 575 currentByte = m_buffer[m_position++]; 576 *value |= ((currentByte & varIntMask) << shift); 577 shift += varIntShift; 578 } while (currentByte & (1 << varIntShift)); 579 return true; 580 } 581 582 const char* m_buffer; 583 const unsigned m_length; 584 unsigned m_position; 585 }; 586 587 class Deserializer { 588 public: 589 explicit Deserializer(Reader& reader) : m_reader(reader) 590 { 591 } 592 593 v8::Local<v8::Value> deserialize() 594 { 595 v8::HandleScope scope; 596 while (!m_reader.isEof()) { 597 if (!doDeserialize()) 598 return v8::Local<v8::Value>(); 599 } 600 if (stackDepth() != 1) 601 return v8::Local<v8::Value>(); 602 return scope.Close(element(0)); 603 } 604 605 private: 606 bool doDeserialize() 607 { 608 SerializationTag tag; 609 v8::Local<v8::Value> value; 610 int length = 0; 611 if (!m_reader.read(&tag, &value, &length)) 612 return false; 613 if (!value.IsEmpty()) { 614 push(value); 615 } else if (tag == ObjectTag) { 616 if (length > stackDepth()) 617 return false; 618 v8::Local<v8::Object> object = v8::Object::New(); 619 for (int i = stackDepth() - length; i < stackDepth(); i += 2) { 620 v8::Local<v8::Value> propertyName = element(i); 621 v8::Local<v8::Value> propertyValue = element(i + 1); 622 object->Set(propertyName, propertyValue); 623 } 624 pop(length); 625 push(object); 626 } else if (tag == ArrayTag) { 627 if (length > stackDepth()) 628 return false; 629 v8::Local<v8::Array> array = v8::Array::New(length); 630 const int depth = stackDepth() - length; 631 { 632 v8::HandleScope scope; 633 for (int i = 0; i < length; ++i) 634 array->Set(v8::Integer::New(i), element(depth + i)); 635 } 636 pop(length); 637 push(array); 638 } else if (tag != PaddingTag) 639 return false; 640 return true; 641 } 642 643 void push(v8::Local<v8::Value> value) { m_stack.append(value); } 644 645 void pop(unsigned length) 646 { 647 ASSERT(length <= m_stack.size()); 648 m_stack.shrink(m_stack.size() - length); 649 } 650 651 int stackDepth() const { return m_stack.size(); } 652 653 v8::Local<v8::Value> element(unsigned index) 654 { 655 ASSERT(index < m_stack.size()); 656 return m_stack[index]; 657 } 658 659 Reader& m_reader; 660 Vector<v8::Local<v8::Value> > m_stack; 661 }; 662 663 } // namespace 664 665 SerializedScriptValue::SerializedScriptValue(v8::Handle<v8::Value> value) 666 { 667 Writer writer; 668 Serializer serializer(writer); 669 if (!serializer.serialize(value)) { 670 // FIXME: throw exception 671 return; 672 } 673 m_data = StringImpl::adopt(writer.data()); 674 } 675 676 SerializedScriptValue::SerializedScriptValue(String data, StringDataMode mode) 677 { 678 if (mode == WireData) 679 m_data = data; 680 else { 681 ASSERT(mode == StringValue); 682 RefPtr<SharedBuffer> buffer = utf8Buffer(data); 683 Writer writer; 684 writer.writeString(buffer->data(), buffer->size()); 685 m_data = StringImpl::adopt(writer.data()); 686 } 687 } 688 689 v8::Local<v8::Value> SerializedScriptValue::deserialize() 690 { 691 if (!m_data.impl()) 692 return v8::Local<v8::Value>(); 693 COMPILE_ASSERT(sizeof(BufferValueType) == 2, BufferValueTypeIsTwoBytes); 694 Reader reader(reinterpret_cast<const char*>(m_data.impl()->characters()), 2 * m_data.length()); 695 Deserializer deserializer(reader); 696 return deserializer.deserialize(); 697 } 698 699 } // namespace WebCore 700