src/3rdparty/v8/src/liveedit.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 #include "v8.h"
  30
  31 #include "liveedit.h"
  32
  33 #include "code-stubs.h"
  34 #include "compilation-cache.h"
  35 #include "compiler.h"
  36 #include "debug.h"
  37 #include "deoptimizer.h"
  38 #include "global-handles.h"
  39 #include "parser.h"
  40 #include "scopeinfo.h"
  41 #include "scopes.h"
  42 #include "v8memory.h"
  43
  44 namespace v8 {
  45 namespace internal {
  46
  47
  48 #ifdef ENABLE_DEBUGGER_SUPPORT
  49
  50
  51 void SetElementNonStrict(Handle<JSObject> object,
  52                          uint32_t index,
  53                          Handle<Object> value) {
  54   // Ignore return value from SetElement. It can only be a failure if there
  55   // are element setters causing exceptions and the debugger context has none
  56   // of these.
  57   Handle<Object> no_failure =
  58       JSObject::SetElement(object, index, value, NONE, kNonStrictMode);
  59   ASSERT(!no_failure.is_null());
  60   USE(no_failure);
  61 }
  62
  63 // A simple implementation of dynamic programming algorithm. It solves
  64 // the problem of finding the difference of 2 arrays. It uses a table of results
  65 // of subproblems. Each cell contains a number together with 2-bit flag
  66 // that helps building the chunk list.
  67 class Differencer {
  68  public:
  69   explicit Differencer(Comparator::Input* input)
  70       : input_(input), len1_(input->GetLength1()), len2_(input->GetLength2()) {
  71     buffer_ = NewArray<int>(len1_ * len2_);
  72   }
  73   ~Differencer() {
  74     DeleteArray(buffer_);
  75   }
  76
  77   void Initialize() {
  78     int array_size = len1_ * len2_;
  79     for (int i = 0; i < array_size; i++) {
  80       buffer_[i] = kEmptyCellValue;
  81     }
  82   }
  83
  84   // Makes sure that result for the full problem is calculated and stored
  85   // in the table together with flags showing a path through subproblems.
  86   void FillTable() {
  87     CompareUpToTail(0, 0);
  88   }
  89
  90   void SaveResult(Comparator::Output* chunk_writer) {
  91     ResultWriter writer(chunk_writer);
  92
  93     int pos1 = 0;
  94     int pos2 = 0;
  95     while (true) {
  96       if (pos1 < len1_) {
  97         if (pos2 < len2_) {
  98           Direction dir = get_direction(pos1, pos2);
  99           switch (dir) {
 100             case EQ:
 101               writer.eq();
 102               pos1++;
 103               pos2++;
 104               break;
 105             case SKIP1:
 106               writer.skip1(1);
 107               pos1++;
 108               break;
 109             case SKIP2:
 110             case SKIP_ANY:
 111               writer.skip2(1);
 112               pos2++;
 113               break;
 114             default:
 115               UNREACHABLE();
 116           }
 117         } else {
 118           writer.skip1(len1_ - pos1);
 119           break;
 120         }
 121       } else {
 122         if (len2_ != pos2) {
 123           writer.skip2(len2_ - pos2);
 124         }
 125         break;
 126       }
 127     }
 128     writer.close();
 129   }
 130
 131  private:
 132   Comparator::Input* input_;
 133   int* buffer_;
 134   int len1_;
 135   int len2_;
 136
 137   enum Direction {
 138     EQ = 0,
 139     SKIP1,
 140     SKIP2,
 141     SKIP_ANY,
 142
 143     MAX_DIRECTION_FLAG_VALUE = SKIP_ANY
 144   };
 145
 146   // Computes result for a subtask and optionally caches it in the buffer table.
 147   // All results values are shifted to make space for flags in the lower bits.
 148   int CompareUpToTail(int pos1, int pos2) {
 149     if (pos1 < len1_) {
 150       if (pos2 < len2_) {
 151         int cached_res = get_value4(pos1, pos2);
 152         if (cached_res == kEmptyCellValue) {
 153           Direction dir;
 154           int res;
 155           if (input_->Equals(pos1, pos2)) {
 156             res = CompareUpToTail(pos1 + 1, pos2 + 1);
 157             dir = EQ;
 158           } else {
 159             int res1 = CompareUpToTail(pos1 + 1, pos2) +
 160                 (1 << kDirectionSizeBits);
 161             int res2 = CompareUpToTail(pos1, pos2 + 1) +
 162                 (1 << kDirectionSizeBits);
 163             if (res1 == res2) {
 164               res = res1;
 165               dir = SKIP_ANY;
 166             } else if (res1 < res2) {
 167               res = res1;
 168               dir = SKIP1;
 169             } else {
 170               res = res2;
 171               dir = SKIP2;
 172             }
 173           }
 174           set_value4_and_dir(pos1, pos2, res, dir);
 175           cached_res = res;
 176         }
 177         return cached_res;
 178       } else {
 179         return (len1_ - pos1) << kDirectionSizeBits;
 180       }
 181     } else {
 182       return (len2_ - pos2) << kDirectionSizeBits;
 183     }
 184   }
 185
 186   inline int& get_cell(int i1, int i2) {
 187     return buffer_[i1 + i2 * len1_];
 188   }
 189
 190   // Each cell keeps a value plus direction. Value is multiplied by 4.
 191   void set_value4_and_dir(int i1, int i2, int value4, Direction dir) {
 192     ASSERT((value4 & kDirectionMask) == 0);
 193     get_cell(i1, i2) = value4 | dir;
 194   }
 195
 196   int get_value4(int i1, int i2) {
 197     return get_cell(i1, i2) & (kMaxUInt32 ^ kDirectionMask);
 198   }
 199   Direction get_direction(int i1, int i2) {
 200     return static_cast<Direction>(get_cell(i1, i2) & kDirectionMask);
 201   }
 202
 203   static const int kDirectionSizeBits = 2;
 204   static const int kDirectionMask = (1 << kDirectionSizeBits) - 1;
 205   static const int kEmptyCellValue = -1 << kDirectionSizeBits;
 206
 207   // This method only holds static assert statement (unfortunately you cannot
 208   // place one in class scope).
 209   void StaticAssertHolder() {
 210     STATIC_ASSERT(MAX_DIRECTION_FLAG_VALUE < (1 << kDirectionSizeBits));
 211   }
 212
 213   class ResultWriter {
 214    public:
 215     explicit ResultWriter(Comparator::Output* chunk_writer)
 216         : chunk_writer_(chunk_writer), pos1_(0), pos2_(0),
 217           pos1_begin_(-1), pos2_begin_(-1), has_open_chunk_(false) {
 218     }
 219     void eq() {
 220       FlushChunk();
 221       pos1_++;
 222       pos2_++;
 223     }
 224     void skip1(int len1) {
 225       StartChunk();
 226       pos1_ += len1;
 227     }
 228     void skip2(int len2) {
 229       StartChunk();
 230       pos2_ += len2;
 231     }
 232     void close() {
 233       FlushChunk();
 234     }
 235
 236    private:
 237     Comparator::Output* chunk_writer_;
 238     int pos1_;
 239     int pos2_;
 240     int pos1_begin_;
 241     int pos2_begin_;
 242     bool has_open_chunk_;
 243
 244     void StartChunk() {
 245       if (!has_open_chunk_) {
 246         pos1_begin_ = pos1_;
 247         pos2_begin_ = pos2_;
 248         has_open_chunk_ = true;
 249       }
 250     }
 251
 252     void FlushChunk() {
 253       if (has_open_chunk_) {
 254         chunk_writer_->AddChunk(pos1_begin_, pos2_begin_,
 255                                 pos1_ - pos1_begin_, pos2_ - pos2_begin_);
 256         has_open_chunk_ = false;
 257       }
 258     }
 259   };
 260 };
 261
 262
 263 void Comparator::CalculateDifference(Comparator::Input* input,
 264                                      Comparator::Output* result_writer) {
 265   Differencer differencer(input);
 266   differencer.Initialize();
 267   differencer.FillTable();
 268   differencer.SaveResult(result_writer);
 269 }
 270
 271
 272 static bool CompareSubstrings(Handle<String> s1, int pos1,
 273                               Handle<String> s2, int pos2, int len) {
 274   for (int i = 0; i < len; i++) {
 275     if (s1->Get(i + pos1) != s2->Get(i + pos2)) {
 276       return false;
 277     }
 278   }
 279   return true;
 280 }
 281
 282
 283 // Additional to Input interface. Lets switch Input range to subrange.
 284 // More elegant way would be to wrap one Input as another Input object
 285 // and translate positions there, but that would cost us additional virtual
 286 // call per comparison.
 287 class SubrangableInput : public Comparator::Input {
 288  public:
 289   virtual void SetSubrange1(int offset, int len) = 0;
 290   virtual void SetSubrange2(int offset, int len) = 0;
 291 };
 292
 293
 294 class SubrangableOutput : public Comparator::Output {
 295  public:
 296   virtual void SetSubrange1(int offset, int len) = 0;
 297   virtual void SetSubrange2(int offset, int len) = 0;
 298 };
 299
 300
 301 static int min(int a, int b) {
 302   return a < b ? a : b;
 303 }
 304
 305
 306 // Finds common prefix and suffix in input. This parts shouldn't take space in
 307 // linear programming table. Enable subranging in input and output.
 308 static void NarrowDownInput(SubrangableInput* input,
 309     SubrangableOutput* output) {
 310   const int len1 = input->GetLength1();
 311   const int len2 = input->GetLength2();
 312
 313   int common_prefix_len;
 314   int common_suffix_len;
 315
 316   {
 317     common_prefix_len = 0;
 318     int prefix_limit = min(len1, len2);
 319     while (common_prefix_len < prefix_limit &&
 320         input->Equals(common_prefix_len, common_prefix_len)) {
 321       common_prefix_len++;
 322     }
 323
 324     common_suffix_len = 0;
 325     int suffix_limit = min(len1 - common_prefix_len, len2 - common_prefix_len);
 326
 327     while (common_suffix_len < suffix_limit &&
 328         input->Equals(len1 - common_suffix_len - 1,
 329         len2 - common_suffix_len - 1)) {
 330       common_suffix_len++;
 331     }
 332   }
 333
 334   if (common_prefix_len > 0 || common_suffix_len > 0) {
 335     int new_len1 = len1 - common_suffix_len - common_prefix_len;
 336     int new_len2 = len2 - common_suffix_len - common_prefix_len;
 337
 338     input->SetSubrange1(common_prefix_len, new_len1);
 339     input->SetSubrange2(common_prefix_len, new_len2);
 340
 341     output->SetSubrange1(common_prefix_len, new_len1);
 342     output->SetSubrange2(common_prefix_len, new_len2);
 343   }
 344 }
 345
 346
 347 // A helper class that writes chunk numbers into JSArray.
 348 // Each chunk is stored as 3 array elements: (pos1_begin, pos1_end, pos2_end).
 349 class CompareOutputArrayWriter {
 350  public:
 351   CompareOutputArrayWriter()
 352       : array_(FACTORY->NewJSArray(10)), current_size_(0) {}
 353
 354   Handle<JSArray> GetResult() {
 355     return array_;
 356   }
 357
 358   void WriteChunk(int char_pos1, int char_pos2, int char_len1, int char_len2) {
 359     SetElementNonStrict(array_,
 360                        current_size_,
 361                        Handle<Object>(Smi::FromInt(char_pos1)));
 362     SetElementNonStrict(array_,
 363                         current_size_ + 1,
 364                         Handle<Object>(Smi::FromInt(char_pos1 + char_len1)));
 365     SetElementNonStrict(array_,
 366                         current_size_ + 2,
 367                         Handle<Object>(Smi::FromInt(char_pos2 + char_len2)));
 368     current_size_ += 3;
 369   }
 370
 371  private:
 372   Handle<JSArray> array_;
 373   int current_size_;
 374 };
 375
 376
 377 // Represents 2 strings as 2 arrays of tokens.
 378 // TODO(LiveEdit): Currently it's actually an array of charactres.
 379 //     Make array of tokens instead.
 380 class TokensCompareInput : public Comparator::Input {
 381  public:
 382   TokensCompareInput(Handle<String> s1, int offset1, int len1,
 383                        Handle<String> s2, int offset2, int len2)
 384       : s1_(s1), offset1_(offset1), len1_(len1),
 385         s2_(s2), offset2_(offset2), len2_(len2) {
 386   }
 387   virtual int GetLength1() {
 388     return len1_;
 389   }
 390   virtual int GetLength2() {
 391     return len2_;
 392   }
 393   bool Equals(int index1, int index2) {
 394     return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
 395   }
 396
 397  private:
 398   Handle<String> s1_;
 399   int offset1_;
 400   int len1_;
 401   Handle<String> s2_;
 402   int offset2_;
 403   int len2_;
 404 };
 405
 406
 407 // Stores compare result in JSArray. Converts substring positions
 408 // to absolute positions.
 409 class TokensCompareOutput : public Comparator::Output {
 410  public:
 411   TokensCompareOutput(CompareOutputArrayWriter* array_writer,
 412                       int offset1, int offset2)
 413         : array_writer_(array_writer), offset1_(offset1), offset2_(offset2) {
 414   }
 415
 416   void AddChunk(int pos1, int pos2, int len1, int len2) {
 417     array_writer_->WriteChunk(pos1 + offset1_, pos2 + offset2_, len1, len2);
 418   }
 419
 420  private:
 421   CompareOutputArrayWriter* array_writer_;
 422   int offset1_;
 423   int offset2_;
 424 };
 425
 426
 427 // Wraps raw n-elements line_ends array as a list of n+1 lines. The last line
 428 // never has terminating new line character.
 429 class LineEndsWrapper {
 430  public:
 431   explicit LineEndsWrapper(Handle<String> string)
 432       : ends_array_(CalculateLineEnds(string, false)),
 433         string_len_(string->length()) {
 434   }
 435   int length() {
 436     return ends_array_->length() + 1;
 437   }
 438   // Returns start for any line including start of the imaginary line after
 439   // the last line.
 440   int GetLineStart(int index) {
 441     if (index == 0) {
 442       return 0;
 443     } else {
 444       return GetLineEnd(index - 1);
 445     }
 446   }
 447   int GetLineEnd(int index) {
 448     if (index == ends_array_->length()) {
 449       // End of the last line is always an end of the whole string.
 450       // If the string ends with a new line character, the last line is an
 451       // empty string after this character.
 452       return string_len_;
 453     } else {
 454       return GetPosAfterNewLine(index);
 455     }
 456   }
 457
 458  private:
 459   Handle<FixedArray> ends_array_;
 460   int string_len_;
 461
 462   int GetPosAfterNewLine(int index) {
 463     return Smi::cast(ends_array_->get(index))->value() + 1;
 464   }
 465 };
 466
 467
 468 // Represents 2 strings as 2 arrays of lines.
 469 class LineArrayCompareInput : public SubrangableInput {
 470  public:
 471   LineArrayCompareInput(Handle<String> s1, Handle<String> s2,
 472                         LineEndsWrapper line_ends1, LineEndsWrapper line_ends2)
 473       : s1_(s1), s2_(s2), line_ends1_(line_ends1),
 474         line_ends2_(line_ends2),
 475         subrange_offset1_(0), subrange_offset2_(0),
 476         subrange_len1_(line_ends1_.length()),
 477         subrange_len2_(line_ends2_.length()) {
 478   }
 479   int GetLength1() {
 480     return subrange_len1_;
 481   }
 482   int GetLength2() {
 483     return subrange_len2_;
 484   }
 485   bool Equals(int index1, int index2) {
 486     index1 += subrange_offset1_;
 487     index2 += subrange_offset2_;
 488
 489     int line_start1 = line_ends1_.GetLineStart(index1);
 490     int line_start2 = line_ends2_.GetLineStart(index2);
 491     int line_end1 = line_ends1_.GetLineEnd(index1);
 492     int line_end2 = line_ends2_.GetLineEnd(index2);
 493     int len1 = line_end1 - line_start1;
 494     int len2 = line_end2 - line_start2;
 495     if (len1 != len2) {
 496       return false;
 497     }
 498     return CompareSubstrings(s1_, line_start1, s2_, line_start2,
 499                              len1);
 500   }
 501   void SetSubrange1(int offset, int len) {
 502     subrange_offset1_ = offset;
 503     subrange_len1_ = len;
 504   }
 505   void SetSubrange2(int offset, int len) {
 506     subrange_offset2_ = offset;
 507     subrange_len2_ = len;
 508   }
 509
 510  private:
 511   Handle<String> s1_;
 512   Handle<String> s2_;
 513   LineEndsWrapper line_ends1_;
 514   LineEndsWrapper line_ends2_;
 515   int subrange_offset1_;
 516   int subrange_offset2_;
 517   int subrange_len1_;
 518   int subrange_len2_;
 519 };
 520
 521
 522 // Stores compare result in JSArray. For each chunk tries to conduct
 523 // a fine-grained nested diff token-wise.
 524 class TokenizingLineArrayCompareOutput : public SubrangableOutput {
 525  public:
 526   TokenizingLineArrayCompareOutput(LineEndsWrapper line_ends1,
 527                                    LineEndsWrapper line_ends2,
 528                                    Handle<String> s1, Handle<String> s2)
 529       : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2),
 530         subrange_offset1_(0), subrange_offset2_(0) {
 531   }
 532
 533   void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) {
 534     line_pos1 += subrange_offset1_;
 535     line_pos2 += subrange_offset2_;
 536
 537     int char_pos1 = line_ends1_.GetLineStart(line_pos1);
 538     int char_pos2 = line_ends2_.GetLineStart(line_pos2);
 539     int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1;
 540     int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) - char_pos2;
 541
 542     if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
 543       // Chunk is small enough to conduct a nested token-level diff.
 544       HandleScope subTaskScope;
 545
 546       TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
 547                                       s2_, char_pos2, char_len2);
 548       TokensCompareOutput tokens_output(&array_writer_, char_pos1,
 549                                           char_pos2);
 550
 551       Comparator::CalculateDifference(&tokens_input, &tokens_output);
 552     } else {
 553       array_writer_.WriteChunk(char_pos1, char_pos2, char_len1, char_len2);
 554     }
 555   }
 556   void SetSubrange1(int offset, int len) {
 557     subrange_offset1_ = offset;
 558   }
 559   void SetSubrange2(int offset, int len) {
 560     subrange_offset2_ = offset;
 561   }
 562
 563   Handle<JSArray> GetResult() {
 564     return array_writer_.GetResult();
 565   }
 566
 567  private:
 568   static const int CHUNK_LEN_LIMIT = 800;
 569
 570   CompareOutputArrayWriter array_writer_;
 571   LineEndsWrapper line_ends1_;
 572   LineEndsWrapper line_ends2_;
 573   Handle<String> s1_;
 574   Handle<String> s2_;
 575   int subrange_offset1_;
 576   int subrange_offset2_;
 577 };
 578
 579
 580 Handle<JSArray> LiveEdit::CompareStrings(Handle<String> s1,
 581                                          Handle<String> s2) {
 582   s1 = FlattenGetString(s1);
 583   s2 = FlattenGetString(s2);
 584
 585   LineEndsWrapper line_ends1(s1);
 586   LineEndsWrapper line_ends2(s2);
 587
 588   LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
 589   TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2);
 590
 591   NarrowDownInput(&input, &output);
 592
 593   Comparator::CalculateDifference(&input, &output);
 594
 595   return output.GetResult();
 596 }
 597
 598
 599 static void CompileScriptForTracker(Isolate* isolate, Handle<Script> script) {
 600   // TODO(635): support extensions.
 601   PostponeInterruptsScope postpone(isolate);
 602
 603   // Build AST.
 604   CompilationInfo info(script);
 605   info.MarkAsGlobal();
 606   // Parse and don't allow skipping lazy functions.
 607   if (ParserApi::Parse(&info, kNoParsingFlags)) {
 608     // Compile the code.
 609     LiveEditFunctionTracker tracker(info.isolate(), info.function());
 610     if (Compiler::MakeCodeForLiveEdit(&info)) {
 611       ASSERT(!info.code().is_null());
 612       tracker.RecordRootFunctionInfo(info.code());
 613     } else {
 614       info.isolate()->StackOverflow();
 615     }
 616   }
 617 }
 618
 619
 620 // Unwraps JSValue object, returning its field "value"
 621 static Handle<Object> UnwrapJSValue(Handle<JSValue> jsValue) {
 622   return Handle<Object>(jsValue->value());
 623 }
 624
 625
 626 // Wraps any object into a OpaqueReference, that will hide the object
 627 // from JavaScript.
 628 static Handle<JSValue> WrapInJSValue(Handle<Object> object) {
 629   Handle<JSFunction> constructor =
 630       Isolate::Current()->opaque_reference_function();
 631   Handle<JSValue> result =
 632       Handle<JSValue>::cast(FACTORY->NewJSObject(constructor));
 633   result->set_value(*object);
 634   return result;
 635 }
 636
 637
 638 // Simple helper class that creates more or less typed structures over
 639 // JSArray object. This is an adhoc method of passing structures from C++
 640 // to JavaScript.
 641 template<typename S>
 642 class JSArrayBasedStruct {
 643  public:
 644   static S Create() {
 645     Handle<JSArray> array = FACTORY->NewJSArray(S::kSize_);
 646     return S(array);
 647   }
 648   static S cast(Object* object) {
 649     JSArray* array = JSArray::cast(object);
 650     Handle<JSArray> array_handle(array);
 651     return S(array_handle);
 652   }
 653   explicit JSArrayBasedStruct(Handle<JSArray> array) : array_(array) {
 654   }
 655   Handle<JSArray> GetJSArray() {
 656     return array_;
 657   }
 658
 659  protected:
 660   void SetField(int field_position, Handle<Object> value) {
 661     SetElementNonStrict(array_, field_position, value);
 662   }
 663   void SetSmiValueField(int field_position, int value) {
 664     SetElementNonStrict(array_,
 665                         field_position,
 666                         Handle<Smi>(Smi::FromInt(value)));
 667   }
 668   Object* GetField(int field_position) {
 669     return array_->GetElementNoExceptionThrown(field_position);
 670   }
 671   int GetSmiValueField(int field_position) {
 672     Object* res = GetField(field_position);
 673     return Smi::cast(res)->value();
 674   }
 675
 676  private:
 677   Handle<JSArray> array_;
 678 };
 679
 680
 681 // Represents some function compilation details. This structure will be used
 682 // from JavaScript. It contains Code object, which is kept wrapped
 683 // into a BlindReference for sanitizing reasons.
 684 class FunctionInfoWrapper : public JSArrayBasedStruct<FunctionInfoWrapper> {
 685  public:
 686   explicit FunctionInfoWrapper(Handle<JSArray> array)
 687       : JSArrayBasedStruct<FunctionInfoWrapper>(array) {
 688   }
 689   void SetInitialProperties(Handle<String> name, int start_position,
 690                             int end_position, int param_num, int parent_index) {
 691     HandleScope scope;
 692     this->SetField(kFunctionNameOffset_, name);
 693     this->SetSmiValueField(kStartPositionOffset_, start_position);
 694     this->SetSmiValueField(kEndPositionOffset_, end_position);
 695     this->SetSmiValueField(kParamNumOffset_, param_num);
 696     this->SetSmiValueField(kParentIndexOffset_, parent_index);
 697   }
 698   void SetFunctionCode(Handle<Code> function_code,
 699       Handle<Object> code_scope_info) {
 700     Handle<JSValue> code_wrapper = WrapInJSValue(function_code);
 701     this->SetField(kCodeOffset_, code_wrapper);
 702
 703     Handle<JSValue> scope_wrapper = WrapInJSValue(code_scope_info);
 704     this->SetField(kCodeScopeInfoOffset_, scope_wrapper);
 705   }
 706   void SetOuterScopeInfo(Handle<Object> scope_info_array) {
 707     this->SetField(kOuterScopeInfoOffset_, scope_info_array);
 708   }
 709   void SetSharedFunctionInfo(Handle<SharedFunctionInfo> info) {
 710     Handle<JSValue> info_holder = WrapInJSValue(info);
 711     this->SetField(kSharedFunctionInfoOffset_, info_holder);
 712   }
 713   int GetParentIndex() {
 714     return this->GetSmiValueField(kParentIndexOffset_);
 715   }
 716   Handle<Code> GetFunctionCode() {
 717     Handle<Object> raw_result = UnwrapJSValue(Handle<JSValue>(
 718         JSValue::cast(this->GetField(kCodeOffset_))));
 719     return Handle<Code>::cast(raw_result);
 720   }
 721   Handle<Object> GetCodeScopeInfo() {
 722     Handle<Object> raw_result = UnwrapJSValue(Handle<JSValue>(
 723         JSValue::cast(this->GetField(kCodeScopeInfoOffset_))));
 724     return raw_result;
 725   }
 726   int GetStartPosition() {
 727     return this->GetSmiValueField(kStartPositionOffset_);
 728   }
 729   int GetEndPosition() {
 730     return this->GetSmiValueField(kEndPositionOffset_);
 731   }
 732
 733  private:
 734   static const int kFunctionNameOffset_ = 0;
 735   static const int kStartPositionOffset_ = 1;
 736   static const int kEndPositionOffset_ = 2;
 737   static const int kParamNumOffset_ = 3;
 738   static const int kCodeOffset_ = 4;
 739   static const int kCodeScopeInfoOffset_ = 5;
 740   static const int kOuterScopeInfoOffset_ = 6;
 741   static const int kParentIndexOffset_ = 7;
 742   static const int kSharedFunctionInfoOffset_ = 8;
 743   static const int kSize_ = 9;
 744
 745   friend class JSArrayBasedStruct<FunctionInfoWrapper>;
 746 };
 747
 748
 749 // Wraps SharedFunctionInfo along with some of its fields for passing it
 750 // back to JavaScript. SharedFunctionInfo object itself is additionally
 751 // wrapped into BlindReference for sanitizing reasons.
 752 class SharedInfoWrapper : public JSArrayBasedStruct<SharedInfoWrapper> {
 753  public:
 754   static bool IsInstance(Handle<JSArray> array) {
 755     return array->length() == Smi::FromInt(kSize_) &&
 756         array->GetElementNoExceptionThrown(kSharedInfoOffset_)->IsJSValue();
 757   }
 758
 759   explicit SharedInfoWrapper(Handle<JSArray> array)
 760       : JSArrayBasedStruct<SharedInfoWrapper>(array) {
 761   }
 762
 763   void SetProperties(Handle<String> name, int start_position, int end_position,
 764                      Handle<SharedFunctionInfo> info) {
 765     HandleScope scope;
 766     this->SetField(kFunctionNameOffset_, name);
 767     Handle<JSValue> info_holder = WrapInJSValue(info);
 768     this->SetField(kSharedInfoOffset_, info_holder);
 769     this->SetSmiValueField(kStartPositionOffset_, start_position);
 770     this->SetSmiValueField(kEndPositionOffset_, end_position);
 771   }
 772   Handle<SharedFunctionInfo> GetInfo() {
 773     Object* element = this->GetField(kSharedInfoOffset_);
 774     Handle<JSValue> value_wrapper(JSValue::cast(element));
 775     Handle<Object> raw_result = UnwrapJSValue(value_wrapper);
 776     return Handle<SharedFunctionInfo>::cast(raw_result);
 777   }
 778
 779  private:
 780   static const int kFunctionNameOffset_ = 0;
 781   static const int kStartPositionOffset_ = 1;
 782   static const int kEndPositionOffset_ = 2;
 783   static const int kSharedInfoOffset_ = 3;
 784   static const int kSize_ = 4;
 785
 786   friend class JSArrayBasedStruct<SharedInfoWrapper>;
 787 };
 788
 789
 790 class FunctionInfoListener {
 791  public:
 792   FunctionInfoListener() {
 793     current_parent_index_ = -1;
 794     len_ = 0;
 795     result_ = FACTORY->NewJSArray(10);
 796   }
 797
 798   void FunctionStarted(FunctionLiteral* fun) {
 799     HandleScope scope;
 800     FunctionInfoWrapper info = FunctionInfoWrapper::Create();
 801     info.SetInitialProperties(fun->name(), fun->start_position(),
 802                               fun->end_position(), fun->parameter_count(),
 803                               current_parent_index_);
 804     current_parent_index_ = len_;
 805     SetElementNonStrict(result_, len_, info.GetJSArray());
 806     len_++;
 807   }
 808
 809   void FunctionDone() {
 810     HandleScope scope;
 811     FunctionInfoWrapper info =
 812         FunctionInfoWrapper::cast(
 813             result_->GetElementNoExceptionThrown(current_parent_index_));
 814     current_parent_index_ = info.GetParentIndex();
 815   }
 816
 817   // Saves only function code, because for a script function we
 818   // may never create a SharedFunctionInfo object.
 819   void FunctionCode(Handle<Code> function_code) {
 820     FunctionInfoWrapper info =
 821         FunctionInfoWrapper::cast(
 822             result_->GetElementNoExceptionThrown(current_parent_index_));
 823     info.SetFunctionCode(function_code, Handle<Object>(HEAP->null_value()));
 824   }
 825
 826   // Saves full information about a function: its code, its scope info
 827   // and a SharedFunctionInfo object.
 828   void FunctionInfo(Handle<SharedFunctionInfo> shared, Scope* scope) {
 829     if (!shared->IsSharedFunctionInfo()) {
 830       return;
 831     }
 832     FunctionInfoWrapper info =
 833         FunctionInfoWrapper::cast(
 834             result_->GetElementNoExceptionThrown(current_parent_index_));
 835     info.SetFunctionCode(Handle<Code>(shared->code()),
 836         Handle<Object>(shared->scope_info()));
 837     info.SetSharedFunctionInfo(shared);
 838
 839     Handle<Object> scope_info_list(SerializeFunctionScope(scope));
 840     info.SetOuterScopeInfo(scope_info_list);
 841   }
 842
 843   Handle<JSArray> GetResult() { return result_; }
 844
 845  private:
 846   Object* SerializeFunctionScope(Scope* scope) {
 847     HandleScope handle_scope;
 848
 849     Handle<JSArray> scope_info_list = FACTORY->NewJSArray(10);
 850     int scope_info_length = 0;
 851
 852     // Saves some description of scope. It stores name and indexes of
 853     // variables in the whole scope chain. Null-named slots delimit
 854     // scopes of this chain.
 855     Scope* outer_scope = scope->outer_scope();
 856     if (outer_scope == NULL) {
 857       return HEAP->undefined_value();
 858     }
 859     do {
 860       ZoneList<Variable*> stack_list(outer_scope->StackLocalCount());
 861       ZoneList<Variable*> context_list(outer_scope->ContextLocalCount());
 862       outer_scope->CollectStackAndContextLocals(&stack_list, &context_list);
 863       context_list.Sort(&Variable::CompareIndex);
 864
 865       for (int i = 0; i < context_list.length(); i++) {
 866         SetElementNonStrict(scope_info_list,
 867                             scope_info_length,
 868                             context_list[i]->name());
 869         scope_info_length++;
 870         SetElementNonStrict(
 871             scope_info_list,
 872             scope_info_length,
 873             Handle<Smi>(Smi::FromInt(context_list[i]->index())));
 874         scope_info_length++;
 875       }
 876       SetElementNonStrict(scope_info_list,
 877                           scope_info_length,
 878                           Handle<Object>(HEAP->null_value()));
 879       scope_info_length++;
 880
 881       outer_scope = outer_scope->outer_scope();
 882     } while (outer_scope != NULL);
 883
 884     return *scope_info_list;
 885   }
 886
 887   Handle<JSArray> result_;
 888   int len_;
 889   int current_parent_index_;
 890 };
 891
 892
 893 JSArray* LiveEdit::GatherCompileInfo(Handle<Script> script,
 894                                      Handle<String> source) {
 895   Isolate* isolate = Isolate::Current();
 896   ZoneScope zone_scope(isolate, DELETE_ON_EXIT);
 897
 898   FunctionInfoListener listener;
 899   Handle<Object> original_source = Handle<Object>(script->source());
 900   script->set_source(*source);
 901   isolate->set_active_function_info_listener(&listener);
 902   CompileScriptForTracker(isolate, script);
 903   isolate->set_active_function_info_listener(NULL);
 904   script->set_source(*original_source);
 905
 906   return *(listener.GetResult());
 907 }
 908
 909
 910 void LiveEdit::WrapSharedFunctionInfos(Handle<JSArray> array) {
 911   HandleScope scope;
 912   int len = Smi::cast(array->length())->value();
 913   for (int i = 0; i < len; i++) {
 914     Handle<SharedFunctionInfo> info(
 915         SharedFunctionInfo::cast(array->GetElementNoExceptionThrown(i)));
 916     SharedInfoWrapper info_wrapper = SharedInfoWrapper::Create();
 917     Handle<String> name_handle(String::cast(info->name()));
 918     info_wrapper.SetProperties(name_handle, info->start_position(),
 919                                info->end_position(), info);
 920     SetElementNonStrict(array, i, info_wrapper.GetJSArray());
 921   }
 922 }
 923
 924
 925 // Visitor that collects all references to a particular code object,
 926 // including "CODE_TARGET" references in other code objects.
 927 // It works in context of ZoneScope.
 928 class ReferenceCollectorVisitor : public ObjectVisitor {
 929  public:
 930   explicit ReferenceCollectorVisitor(Code* original)
 931     : original_(original), rvalues_(10), reloc_infos_(10), code_entries_(10) {
 932   }
 933
 934   virtual void VisitPointers(Object** start, Object** end) {
 935     for (Object** p = start; p < end; p++) {
 936       if (*p == original_) {
 937         rvalues_.Add(p);
 938       }
 939     }
 940   }
 941
 942   virtual void VisitCodeEntry(Address entry) {
 943     if (Code::GetObjectFromEntryAddress(entry) == original_) {
 944       code_entries_.Add(entry);
 945     }
 946   }
 947
 948   virtual void VisitCodeTarget(RelocInfo* rinfo) {
 949     if (RelocInfo::IsCodeTarget(rinfo->rmode()) &&
 950         Code::GetCodeFromTargetAddress(rinfo->target_address()) == original_) {
 951       reloc_infos_.Add(*rinfo);
 952     }
 953   }
 954
 955   virtual void VisitDebugTarget(RelocInfo* rinfo) {
 956     VisitCodeTarget(rinfo);
 957   }
 958
 959   // Post-visiting method that iterates over all collected references and
 960   // modifies them.
 961   void Replace(Code* substitution) {
 962     for (int i = 0; i < rvalues_.length(); i++) {
 963       *(rvalues_[i]) = substitution;
 964     }
 965     Address substitution_entry = substitution->instruction_start();
 966     for (int i = 0; i < reloc_infos_.length(); i++) {
 967       reloc_infos_[i].set_target_address(substitution_entry);
 968     }
 969     for (int i = 0; i < code_entries_.length(); i++) {
 970       Address entry = code_entries_[i];
 971       Memory::Address_at(entry) = substitution_entry;
 972     }
 973   }
 974
 975  private:
 976   Code* original_;
 977   ZoneList<Object**> rvalues_;
 978   ZoneList<RelocInfo> reloc_infos_;
 979   ZoneList<Address> code_entries_;
 980 };
 981
 982
 983 // Finds all references to original and replaces them with substitution.
 984 static void ReplaceCodeObject(Code* original, Code* substitution) {
 985   ASSERT(!HEAP->InNewSpace(substitution));
 986
 987   HeapIterator iterator;
 988   AssertNoAllocation no_allocations_please;
 989
 990   // A zone scope for ReferenceCollectorVisitor.
 991   ZoneScope scope(Isolate::Current(), DELETE_ON_EXIT);
 992
 993   ReferenceCollectorVisitor visitor(original);
 994
 995   // Iterate over all roots. Stack frames may have pointer into original code,
 996   // so temporary replace the pointers with offset numbers
 997   // in prologue/epilogue.
 998   {
 999     HEAP->IterateStrongRoots(&visitor, VISIT_ALL);
1000   }
1001
1002   // Now iterate over all pointers of all objects, including code_target
1003   // implicit pointers.
1004   for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
1005     obj->Iterate(&visitor);
1006   }
1007
1008   visitor.Replace(substitution);
1009 }
1010
1011
1012 // Check whether the code is natural function code (not a lazy-compile stub
1013 // code).
1014 static bool IsJSFunctionCode(Code* code) {
1015   return code->kind() == Code::FUNCTION;
1016 }
1017
1018
1019 // Returns true if an instance of candidate were inlined into function's code.
1020 static bool IsInlined(JSFunction* function, SharedFunctionInfo* candidate) {
1021   AssertNoAllocation no_gc;
1022
1023   if (function->code()->kind() != Code::OPTIMIZED_FUNCTION) return false;
1024
1025   DeoptimizationInputData* data =
1026       DeoptimizationInputData::cast(function->code()->deoptimization_data());
1027
1028   if (data == HEAP->empty_fixed_array()) return false;
1029
1030   FixedArray* literals = data->LiteralArray();
1031
1032   int inlined_count = data->InlinedFunctionCount()->value();
1033   for (int i = 0; i < inlined_count; ++i) {
1034     JSFunction* inlined = JSFunction::cast(literals->get(i));
1035     if (inlined->shared() == candidate) return true;
1036   }
1037
1038   return false;
1039 }
1040
1041
1042 class DependentFunctionsDeoptimizingVisitor : public OptimizedFunctionVisitor {
1043  public:
1044   explicit DependentFunctionsDeoptimizingVisitor(
1045       SharedFunctionInfo* function_info)
1046       : function_info_(function_info) {}
1047
1048   virtual void EnterContext(Context* context) {
1049   }
1050
1051   virtual void VisitFunction(JSFunction* function) {
1052     if (function->shared() == function_info_ ||
1053         IsInlined(function, function_info_)) {
1054       Deoptimizer::DeoptimizeFunction(function);
1055     }
1056   }
1057
1058   virtual void LeaveContext(Context* context) {
1059   }
1060
1061  private:
1062   SharedFunctionInfo* function_info_;
1063 };
1064
1065
1066 static void DeoptimizeDependentFunctions(SharedFunctionInfo* function_info) {
1067   AssertNoAllocation no_allocation;
1068
1069   DependentFunctionsDeoptimizingVisitor visitor(function_info);
1070   Deoptimizer::VisitAllOptimizedFunctions(&visitor);
1071 }
1072
1073
1074 MaybeObject* LiveEdit::ReplaceFunctionCode(
1075     Handle<JSArray> new_compile_info_array,
1076     Handle<JSArray> shared_info_array) {
1077   HandleScope scope;
1078
1079   if (!SharedInfoWrapper::IsInstance(shared_info_array)) {
1080     return Isolate::Current()->ThrowIllegalOperation();
1081   }
1082
1083   FunctionInfoWrapper compile_info_wrapper(new_compile_info_array);
1084   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1085
1086   Handle<SharedFunctionInfo> shared_info = shared_info_wrapper.GetInfo();
1087
1088   HEAP->EnsureHeapIsIterable();
1089
1090   if (IsJSFunctionCode(shared_info->code())) {
1091     Handle<Code> code = compile_info_wrapper.GetFunctionCode();
1092     ReplaceCodeObject(shared_info->code(), *code);
1093     Handle<Object> code_scope_info =  compile_info_wrapper.GetCodeScopeInfo();
1094     if (code_scope_info->IsFixedArray()) {
1095       shared_info->set_scope_info(ScopeInfo::cast(*code_scope_info));
1096     }
1097   }
1098
1099   if (shared_info->debug_info()->IsDebugInfo()) {
1100     Handle<DebugInfo> debug_info(DebugInfo::cast(shared_info->debug_info()));
1101     Handle<Code> new_original_code =
1102         FACTORY->CopyCode(compile_info_wrapper.GetFunctionCode());
1103     debug_info->set_original_code(*new_original_code);
1104   }
1105
1106   int start_position = compile_info_wrapper.GetStartPosition();
1107   int end_position = compile_info_wrapper.GetEndPosition();
1108   shared_info->set_start_position(start_position);
1109   shared_info->set_end_position(end_position);
1110
1111   shared_info->set_construct_stub(
1112       Isolate::Current()->builtins()->builtin(
1113           Builtins::kJSConstructStubGeneric));
1114
1115   DeoptimizeDependentFunctions(*shared_info);
1116   Isolate::Current()->compilation_cache()->Remove(shared_info);
1117
1118   return HEAP->undefined_value();
1119 }
1120
1121
1122 MaybeObject* LiveEdit::FunctionSourceUpdated(
1123     Handle<JSArray> shared_info_array) {
1124   HandleScope scope;
1125
1126   if (!SharedInfoWrapper::IsInstance(shared_info_array)) {
1127     return Isolate::Current()->ThrowIllegalOperation();
1128   }
1129
1130   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1131   Handle<SharedFunctionInfo> shared_info = shared_info_wrapper.GetInfo();
1132
1133   DeoptimizeDependentFunctions(*shared_info);
1134   Isolate::Current()->compilation_cache()->Remove(shared_info);
1135
1136   return HEAP->undefined_value();
1137 }
1138
1139
1140 void LiveEdit::SetFunctionScript(Handle<JSValue> function_wrapper,
1141                                  Handle<Object> script_handle) {
1142   Handle<SharedFunctionInfo> shared_info =
1143       Handle<SharedFunctionInfo>::cast(UnwrapJSValue(function_wrapper));
1144   shared_info->set_script(*script_handle);
1145
1146   Isolate::Current()->compilation_cache()->Remove(shared_info);
1147 }
1148
1149
1150 // For a script text change (defined as position_change_array), translates
1151 // position in unchanged text to position in changed text.
1152 // Text change is a set of non-overlapping regions in text, that have changed
1153 // their contents and length. It is specified as array of groups of 3 numbers:
1154 // (change_begin, change_end, change_end_new_position).
1155 // Each group describes a change in text; groups are sorted by change_begin.
1156 // Only position in text beyond any changes may be successfully translated.
1157 // If a positions is inside some region that changed, result is currently
1158 // undefined.
1159 static int TranslatePosition(int original_position,
1160                              Handle<JSArray> position_change_array) {
1161   int position_diff = 0;
1162   int array_len = Smi::cast(position_change_array->length())->value();
1163   // TODO(635): binary search may be used here
1164   for (int i = 0; i < array_len; i += 3) {
1165     Object* element = position_change_array->GetElementNoExceptionThrown(i);
1166     int chunk_start = Smi::cast(element)->value();
1167     if (original_position < chunk_start) {
1168       break;
1169     }
1170     element = position_change_array->GetElementNoExceptionThrown(i + 1);
1171     int chunk_end = Smi::cast(element)->value();
1172     // Position mustn't be inside a chunk.
1173     ASSERT(original_position >= chunk_end);
1174     element = position_change_array->GetElementNoExceptionThrown(i + 2);
1175     int chunk_changed_end = Smi::cast(element)->value();
1176     position_diff = chunk_changed_end - chunk_end;
1177   }
1178
1179   return original_position + position_diff;
1180 }
1181
1182
1183 // Auto-growing buffer for writing relocation info code section. This buffer
1184 // is a simplified version of buffer from Assembler. Unlike Assembler, this
1185 // class is platform-independent and it works without dealing with instructions.
1186 // As specified by RelocInfo format, the buffer is filled in reversed order:
1187 // from upper to lower addresses.
1188 // It uses NewArray/DeleteArray for memory management.
1189 class RelocInfoBuffer {
1190  public:
1191   RelocInfoBuffer(int buffer_initial_capicity, byte* pc) {
1192     buffer_size_ = buffer_initial_capicity + kBufferGap;
1193     buffer_ = NewArray<byte>(buffer_size_);
1194
1195     reloc_info_writer_.Reposition(buffer_ + buffer_size_, pc);
1196   }
1197   ~RelocInfoBuffer() {
1198     DeleteArray(buffer_);
1199   }
1200
1201   // As specified by RelocInfo format, the buffer is filled in reversed order:
1202   // from upper to lower addresses.
1203   void Write(const RelocInfo* rinfo) {
1204     if (buffer_ + kBufferGap >= reloc_info_writer_.pos()) {
1205       Grow();
1206     }
1207     reloc_info_writer_.Write(rinfo);
1208   }
1209
1210   Vector<byte> GetResult() {
1211     // Return the bytes from pos up to end of buffer.
1212     int result_size =
1213         static_cast<int>((buffer_ + buffer_size_) - reloc_info_writer_.pos());
1214     return Vector<byte>(reloc_info_writer_.pos(), result_size);
1215   }
1216
1217  private:
1218   void Grow() {
1219     // Compute new buffer size.
1220     int new_buffer_size;
1221     if (buffer_size_ < 2 * KB) {
1222       new_buffer_size = 4 * KB;
1223     } else {
1224       new_buffer_size = 2 * buffer_size_;
1225     }
1226     // Some internal data structures overflow for very large buffers,
1227     // they must ensure that kMaximalBufferSize is not too large.
1228     if (new_buffer_size > kMaximalBufferSize) {
1229       V8::FatalProcessOutOfMemory("RelocInfoBuffer::GrowBuffer");
1230     }
1231
1232     // Set up new buffer.
1233     byte* new_buffer = NewArray<byte>(new_buffer_size);
1234
1235     // Copy the data.
1236     int curently_used_size =
1237         static_cast<int>(buffer_ + buffer_size_ - reloc_info_writer_.pos());
1238     memmove(new_buffer + new_buffer_size - curently_used_size,
1239             reloc_info_writer_.pos(), curently_used_size);
1240
1241     reloc_info_writer_.Reposition(
1242         new_buffer + new_buffer_size - curently_used_size,
1243         reloc_info_writer_.last_pc());
1244
1245     DeleteArray(buffer_);
1246     buffer_ = new_buffer;
1247     buffer_size_ = new_buffer_size;
1248   }
1249
1250   RelocInfoWriter reloc_info_writer_;
1251   byte* buffer_;
1252   int buffer_size_;
1253
1254   static const int kBufferGap = RelocInfoWriter::kMaxSize;
1255   static const int kMaximalBufferSize = 512*MB;
1256 };
1257
1258 // Patch positions in code (changes relocation info section) and possibly
1259 // returns new instance of code.
1260 static Handle<Code> PatchPositionsInCode(
1261     Handle<Code> code,
1262     Handle<JSArray> position_change_array) {
1263
1264   RelocInfoBuffer buffer_writer(code->relocation_size(),
1265                                 code->instruction_start());
1266
1267   {
1268     AssertNoAllocation no_allocations_please;
1269     for (RelocIterator it(*code); !it.done(); it.next()) {
1270       RelocInfo* rinfo = it.rinfo();
1271       if (RelocInfo::IsPosition(rinfo->rmode())) {
1272         int position = static_cast<int>(rinfo->data());
1273         int new_position = TranslatePosition(position,
1274                                              position_change_array);
1275         if (position != new_position) {
1276           RelocInfo info_copy(rinfo->pc(), rinfo->rmode(), new_position, NULL);
1277           buffer_writer.Write(&info_copy);
1278           continue;
1279         }
1280       }
1281       buffer_writer.Write(it.rinfo());
1282     }
1283   }
1284
1285   Vector<byte> buffer = buffer_writer.GetResult();
1286
1287   if (buffer.length() == code->relocation_size()) {
1288     // Simply patch relocation area of code.
1289     memcpy(code->relocation_start(), buffer.start(), buffer.length());
1290     return code;
1291   } else {
1292     // Relocation info section now has different size. We cannot simply
1293     // rewrite it inside code object. Instead we have to create a new
1294     // code object.
1295     Handle<Code> result(FACTORY->CopyCode(code, buffer));
1296     return result;
1297   }
1298 }
1299
1300
1301 MaybeObject* LiveEdit::PatchFunctionPositions(
1302     Handle<JSArray> shared_info_array, Handle<JSArray> position_change_array) {
1303
1304   if (!SharedInfoWrapper::IsInstance(shared_info_array)) {
1305     return Isolate::Current()->ThrowIllegalOperation();
1306   }
1307
1308   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1309   Handle<SharedFunctionInfo> info = shared_info_wrapper.GetInfo();
1310
1311   int old_function_start = info->start_position();
1312   int new_function_start = TranslatePosition(old_function_start,
1313                                              position_change_array);
1314   int new_function_end = TranslatePosition(info->end_position(),
1315                                            position_change_array);
1316   int new_function_token_pos =
1317       TranslatePosition(info->function_token_position(), position_change_array);
1318
1319   info->set_start_position(new_function_start);
1320   info->set_end_position(new_function_end);
1321   info->set_function_token_position(new_function_token_pos);
1322
1323   HEAP->EnsureHeapIsIterable();
1324
1325   if (IsJSFunctionCode(info->code())) {
1326     // Patch relocation info section of the code.
1327     Handle<Code> patched_code = PatchPositionsInCode(Handle<Code>(info->code()),
1328                                                      position_change_array);
1329     if (*patched_code != info->code()) {
1330       // Replace all references to the code across the heap. In particular,
1331       // some stubs may refer to this code and this code may be being executed
1332       // on stack (it is safe to substitute the code object on stack, because
1333       // we only change the structure of rinfo and leave instructions
1334       // untouched).
1335       ReplaceCodeObject(info->code(), *patched_code);
1336     }
1337   }
1338
1339   return HEAP->undefined_value();
1340 }
1341
1342
1343 static Handle<Script> CreateScriptCopy(Handle<Script> original) {
1344   Handle<String> original_source(String::cast(original->source()));
1345
1346   Handle<Script> copy = FACTORY->NewScript(original_source);
1347
1348   copy->set_name(original->name());
1349   copy->set_line_offset(original->line_offset());
1350   copy->set_column_offset(original->column_offset());
1351   copy->set_data(original->data());
1352   copy->set_type(original->type());
1353   copy->set_context_data(original->context_data());
1354   copy->set_compilation_type(original->compilation_type());
1355   copy->set_eval_from_shared(original->eval_from_shared());
1356   copy->set_eval_from_instructions_offset(
1357       original->eval_from_instructions_offset());
1358
1359   return copy;
1360 }
1361
1362
1363 Object* LiveEdit::ChangeScriptSource(Handle<Script> original_script,
1364                                      Handle<String> new_source,
1365                                      Handle<Object> old_script_name) {
1366   Handle<Object> old_script_object;
1367   if (old_script_name->IsString()) {
1368     Handle<Script> old_script = CreateScriptCopy(original_script);
1369     old_script->set_name(String::cast(*old_script_name));
1370     old_script_object = old_script;
1371     Isolate::Current()->debugger()->OnAfterCompile(
1372         old_script, Debugger::SEND_WHEN_DEBUGGING);
1373   } else {
1374     old_script_object = Handle<Object>(HEAP->null_value());
1375   }
1376
1377   original_script->set_source(*new_source);
1378
1379   // Drop line ends so that they will be recalculated.
1380   original_script->set_line_ends(HEAP->undefined_value());
1381
1382   return *old_script_object;
1383 }
1384
1385
1386
1387 void LiveEdit::ReplaceRefToNestedFunction(
1388     Handle<JSValue> parent_function_wrapper,
1389     Handle<JSValue> orig_function_wrapper,
1390     Handle<JSValue> subst_function_wrapper) {
1391
1392   Handle<SharedFunctionInfo> parent_shared =
1393       Handle<SharedFunctionInfo>::cast(UnwrapJSValue(parent_function_wrapper));
1394   Handle<SharedFunctionInfo> orig_shared =
1395       Handle<SharedFunctionInfo>::cast(UnwrapJSValue(orig_function_wrapper));
1396   Handle<SharedFunctionInfo> subst_shared =
1397       Handle<SharedFunctionInfo>::cast(UnwrapJSValue(subst_function_wrapper));
1398
1399   for (RelocIterator it(parent_shared->code()); !it.done(); it.next()) {
1400     if (it.rinfo()->rmode() == RelocInfo::EMBEDDED_OBJECT) {
1401       if (it.rinfo()->target_object() == *orig_shared) {
1402         it.rinfo()->set_target_object(*subst_shared);
1403       }
1404     }
1405   }
1406 }
1407
1408
1409 // Check an activation against list of functions. If there is a function
1410 // that matches, its status in result array is changed to status argument value.
1411 static bool CheckActivation(Handle<JSArray> shared_info_array,
1412                             Handle<JSArray> result,
1413                             StackFrame* frame,
1414                             LiveEdit::FunctionPatchabilityStatus status) {
1415   if (!frame->is_java_script()) return false;
1416
1417   Handle<JSFunction> function(
1418       JSFunction::cast(JavaScriptFrame::cast(frame)->function()));
1419
1420   int len = Smi::cast(shared_info_array->length())->value();
1421   for (int i = 0; i < len; i++) {
1422     JSValue* wrapper =
1423         JSValue::cast(shared_info_array->GetElementNoExceptionThrown(i));
1424     Handle<SharedFunctionInfo> shared(
1425         SharedFunctionInfo::cast(wrapper->value()));
1426
1427     if (function->shared() == *shared || IsInlined(*function, *shared)) {
1428       SetElementNonStrict(result, i, Handle<Smi>(Smi::FromInt(status)));
1429       return true;
1430     }
1431   }
1432   return false;
1433 }
1434
1435
1436 // Iterates over handler chain and removes all elements that are inside
1437 // frames being dropped.
1438 static bool FixTryCatchHandler(StackFrame* top_frame,
1439                                StackFrame* bottom_frame) {
1440   Address* pointer_address =
1441       &Memory::Address_at(Isolate::Current()->get_address_from_id(
1442           Isolate::kHandlerAddress));
1443
1444   while (*pointer_address < top_frame->sp()) {
1445     pointer_address = &Memory::Address_at(*pointer_address);
1446   }
1447   Address* above_frame_address = pointer_address;
1448   while (*pointer_address < bottom_frame->fp()) {
1449     pointer_address = &Memory::Address_at(*pointer_address);
1450   }
1451   bool change = *above_frame_address != *pointer_address;
1452   *above_frame_address = *pointer_address;
1453   return change;
1454 }
1455
1456
1457 // Removes specified range of frames from stack. There may be 1 or more
1458 // frames in range. Anyway the bottom frame is restarted rather than dropped,
1459 // and therefore has to be a JavaScript frame.
1460 // Returns error message or NULL.
1461 static const char* DropFrames(Vector<StackFrame*> frames,
1462                               int top_frame_index,
1463                               int bottom_js_frame_index,
1464                               Debug::FrameDropMode* mode,
1465                               Object*** restarter_frame_function_pointer) {
1466   if (!Debug::kFrameDropperSupported) {
1467     return "Stack manipulations are not supported in this architecture.";
1468   }
1469
1470   StackFrame* pre_top_frame = frames[top_frame_index - 1];
1471   StackFrame* top_frame = frames[top_frame_index];
1472   StackFrame* bottom_js_frame = frames[bottom_js_frame_index];
1473
1474   ASSERT(bottom_js_frame->is_java_script());
1475
1476   // Check the nature of the top frame.
1477   Isolate* isolate = Isolate::Current();
1478   Code* pre_top_frame_code = pre_top_frame->LookupCode();
1479   bool frame_has_padding;
1480   if (pre_top_frame_code->is_inline_cache_stub() &&
1481       pre_top_frame_code->ic_state() == DEBUG_BREAK) {
1482     // OK, we can drop inline cache calls.
1483     *mode = Debug::FRAME_DROPPED_IN_IC_CALL;
1484     frame_has_padding = Debug::FramePaddingLayout::kIsSupported;
1485   } else if (pre_top_frame_code ==
1486              isolate->debug()->debug_break_slot()) {
1487     // OK, we can drop debug break slot.
1488     *mode = Debug::FRAME_DROPPED_IN_DEBUG_SLOT_CALL;
1489     frame_has_padding = Debug::FramePaddingLayout::kIsSupported;
1490   } else if (pre_top_frame_code ==
1491       isolate->builtins()->builtin(
1492           Builtins::kFrameDropper_LiveEdit)) {
1493     // OK, we can drop our own code.
1494     *mode = Debug::FRAME_DROPPED_IN_DIRECT_CALL;
1495     frame_has_padding = false;
1496   } else if (pre_top_frame_code ==
1497       isolate->builtins()->builtin(Builtins::kReturn_DebugBreak)) {
1498     *mode = Debug::FRAME_DROPPED_IN_RETURN_CALL;
1499     frame_has_padding = Debug::FramePaddingLayout::kIsSupported;
1500   } else if (pre_top_frame_code->kind() == Code::STUB &&
1501       pre_top_frame_code->major_key() == CodeStub::CEntry) {
1502     // Entry from our unit tests on 'debugger' statement.
1503     // It's fine, we support this case.
1504     *mode = Debug::FRAME_DROPPED_IN_DIRECT_CALL;
1505     // We don't have a padding from 'debugger' statement call.
1506     // Here the stub is CEntry, it's not debug-only and can't be padded.
1507     // If anyone would complain, a proxy padded stub could be added.
1508     frame_has_padding = false;
1509   } else {
1510     return "Unknown structure of stack above changing function";
1511   }
1512
1513   Address unused_stack_top = top_frame->sp();
1514   Address unused_stack_bottom = bottom_js_frame->fp()
1515       - Debug::kFrameDropperFrameSize * kPointerSize  // Size of the new frame.
1516       + kPointerSize;  // Bigger address end is exclusive.
1517
1518   Address* top_frame_pc_address = top_frame->pc_address();
1519
1520   // top_frame may be damaged below this point. Do not used it.
1521   ASSERT(!(top_frame = NULL));
1522
1523   if (unused_stack_top > unused_stack_bottom) {
1524     if (frame_has_padding) {
1525       int shortage_bytes =
1526           static_cast<int>(unused_stack_top - unused_stack_bottom);
1527
1528       Address padding_start = pre_top_frame->fp() -
1529           Debug::FramePaddingLayout::kFrameBaseSize * kPointerSize;
1530
1531       Address padding_pointer = padding_start;
1532       Smi* padding_object =
1533           Smi::FromInt(Debug::FramePaddingLayout::kPaddingValue);
1534       while (Memory::Object_at(padding_pointer) == padding_object) {
1535         padding_pointer -= kPointerSize;
1536       }
1537       int padding_counter =
1538           Smi::cast(Memory::Object_at(padding_pointer))->value();
1539       if (padding_counter * kPointerSize < shortage_bytes) {
1540         return "Not enough space for frame dropper frame "
1541             "(even with padding frame)";
1542       }
1543       Memory::Object_at(padding_pointer) =
1544           Smi::FromInt(padding_counter - shortage_bytes / kPointerSize);
1545
1546       StackFrame* pre_pre_frame = frames[top_frame_index - 2];
1547
1548       memmove(padding_start + kPointerSize - shortage_bytes,
1549           padding_start + kPointerSize,
1550           Debug::FramePaddingLayout::kFrameBaseSize * kPointerSize);
1551
1552       pre_top_frame->UpdateFp(pre_top_frame->fp() - shortage_bytes);
1553       pre_pre_frame->SetCallerFp(pre_top_frame->fp());
1554       unused_stack_top -= shortage_bytes;
1555
1556       STATIC_ASSERT(sizeof(Address) == kPointerSize);
1557       top_frame_pc_address -= shortage_bytes / kPointerSize;
1558     } else {
1559       return "Not enough space for frame dropper frame";
1560     }
1561   }
1562
1563   // Committing now. After this point we should return only NULL value.
1564
1565   FixTryCatchHandler(pre_top_frame, bottom_js_frame);
1566   // Make sure FixTryCatchHandler is idempotent.
1567   ASSERT(!FixTryCatchHandler(pre_top_frame, bottom_js_frame));
1568
1569   Handle<Code> code = Isolate::Current()->builtins()->FrameDropper_LiveEdit();
1570   *top_frame_pc_address = code->entry();
1571   pre_top_frame->SetCallerFp(bottom_js_frame->fp());
1572
1573   *restarter_frame_function_pointer =
1574       Debug::SetUpFrameDropperFrame(bottom_js_frame, code);
1575
1576   ASSERT((**restarter_frame_function_pointer)->IsJSFunction());
1577
1578   for (Address a = unused_stack_top;
1579       a < unused_stack_bottom;
1580       a += kPointerSize) {
1581     Memory::Object_at(a) = Smi::FromInt(0);
1582   }
1583
1584   return NULL;
1585 }
1586
1587
1588 static bool IsDropableFrame(StackFrame* frame) {
1589   return !frame->is_exit();
1590 }
1591
1592 // Fills result array with statuses of functions. Modifies the stack
1593 // removing all listed function if possible and if do_drop is true.
1594 static const char* DropActivationsInActiveThread(
1595     Handle<JSArray> shared_info_array, Handle<JSArray> result, bool do_drop) {
1596   Isolate* isolate = Isolate::Current();
1597   Debug* debug = isolate->debug();
1598   ZoneScope scope(isolate, DELETE_ON_EXIT);
1599   Vector<StackFrame*> frames = CreateStackMap();
1600
1601   int array_len = Smi::cast(shared_info_array->length())->value();
1602
1603   int top_frame_index = -1;
1604   int frame_index = 0;
1605   for (; frame_index < frames.length(); frame_index++) {
1606     StackFrame* frame = frames[frame_index];
1607     if (frame->id() == debug->break_frame_id()) {
1608       top_frame_index = frame_index;
1609       break;
1610     }
1611     if (CheckActivation(shared_info_array, result, frame,
1612                         LiveEdit::FUNCTION_BLOCKED_UNDER_NATIVE_CODE)) {
1613       // We are still above break_frame. It is not a target frame,
1614       // it is a problem.
1615       return "Debugger mark-up on stack is not found";
1616     }
1617   }
1618
1619   if (top_frame_index == -1) {
1620     // We haven't found break frame, but no function is blocking us anyway.
1621     return NULL;
1622   }
1623
1624   bool target_frame_found = false;
1625   int bottom_js_frame_index = top_frame_index;
1626   bool c_code_found = false;
1627
1628   for (; frame_index < frames.length(); frame_index++) {
1629     StackFrame* frame = frames[frame_index];
1630     if (!IsDropableFrame(frame)) {
1631       c_code_found = true;
1632       break;
1633     }
1634     if (CheckActivation(shared_info_array, result, frame,
1635                         LiveEdit::FUNCTION_BLOCKED_ON_ACTIVE_STACK)) {
1636       target_frame_found = true;
1637       bottom_js_frame_index = frame_index;
1638     }
1639   }
1640
1641   if (c_code_found) {
1642     // There is a C frames on stack. Check that there are no target frames
1643     // below them.
1644     for (; frame_index < frames.length(); frame_index++) {
1645       StackFrame* frame = frames[frame_index];
1646       if (frame->is_java_script()) {
1647         if (CheckActivation(shared_info_array, result, frame,
1648                             LiveEdit::FUNCTION_BLOCKED_UNDER_NATIVE_CODE)) {
1649           // Cannot drop frame under C frames.
1650           return NULL;
1651         }
1652       }
1653     }
1654   }
1655
1656   if (!do_drop) {
1657     // We are in check-only mode.
1658     return NULL;
1659   }
1660
1661   if (!target_frame_found) {
1662     // Nothing to drop.
1663     return NULL;
1664   }
1665
1666   Debug::FrameDropMode drop_mode = Debug::FRAMES_UNTOUCHED;
1667   Object** restarter_frame_function_pointer = NULL;
1668   const char* error_message = DropFrames(frames, top_frame_index,
1669                                          bottom_js_frame_index, &drop_mode,
1670                                          &restarter_frame_function_pointer);
1671
1672   if (error_message != NULL) {
1673     return error_message;
1674   }
1675
1676   // Adjust break_frame after some frames has been dropped.
1677   StackFrame::Id new_id = StackFrame::NO_ID;
1678   for (int i = bottom_js_frame_index + 1; i < frames.length(); i++) {
1679     if (frames[i]->type() == StackFrame::JAVA_SCRIPT) {
1680       new_id = frames[i]->id();
1681       break;
1682     }
1683   }
1684   debug->FramesHaveBeenDropped(new_id, drop_mode,
1685                                restarter_frame_function_pointer);
1686
1687   // Replace "blocked on active" with "replaced on active" status.
1688   for (int i = 0; i < array_len; i++) {
1689     if (result->GetElement(i) ==
1690         Smi::FromInt(LiveEdit::FUNCTION_BLOCKED_ON_ACTIVE_STACK)) {
1691       Handle<Object> replaced(
1692           Smi::FromInt(LiveEdit::FUNCTION_REPLACED_ON_ACTIVE_STACK));
1693       SetElementNonStrict(result, i, replaced);
1694     }
1695   }
1696   return NULL;
1697 }
1698
1699
1700 class InactiveThreadActivationsChecker : public ThreadVisitor {
1701  public:
1702   InactiveThreadActivationsChecker(Handle<JSArray> shared_info_array,
1703                                    Handle<JSArray> result)
1704       : shared_info_array_(shared_info_array), result_(result),
1705         has_blocked_functions_(false) {
1706   }
1707   void VisitThread(Isolate* isolate, ThreadLocalTop* top) {
1708     for (StackFrameIterator it(isolate, top); !it.done(); it.Advance()) {
1709       has_blocked_functions_ |= CheckActivation(
1710           shared_info_array_, result_, it.frame(),
1711           LiveEdit::FUNCTION_BLOCKED_ON_OTHER_STACK);
1712     }
1713   }
1714   bool HasBlockedFunctions() {
1715     return has_blocked_functions_;
1716   }
1717
1718  private:
1719   Handle<JSArray> shared_info_array_;
1720   Handle<JSArray> result_;
1721   bool has_blocked_functions_;
1722 };
1723
1724
1725 Handle<JSArray> LiveEdit::CheckAndDropActivations(
1726     Handle<JSArray> shared_info_array, bool do_drop) {
1727   int len = Smi::cast(shared_info_array->length())->value();
1728
1729   Handle<JSArray> result = FACTORY->NewJSArray(len);
1730
1731   // Fill the default values.
1732   for (int i = 0; i < len; i++) {
1733     SetElementNonStrict(
1734         result,
1735         i,
1736         Handle<Smi>(Smi::FromInt(FUNCTION_AVAILABLE_FOR_PATCH)));
1737   }
1738
1739
1740   // First check inactive threads. Fail if some functions are blocked there.
1741   InactiveThreadActivationsChecker inactive_threads_checker(shared_info_array,
1742                                                             result);
1743   Isolate::Current()->thread_manager()->IterateArchivedThreads(
1744       &inactive_threads_checker);
1745   if (inactive_threads_checker.HasBlockedFunctions()) {
1746     return result;
1747   }
1748
1749   // Try to drop activations from the current stack.
1750   const char* error_message =
1751       DropActivationsInActiveThread(shared_info_array, result, do_drop);
1752   if (error_message != NULL) {
1753     // Add error message as an array extra element.
1754     Vector<const char> vector_message(error_message, StrLength(error_message));
1755     Handle<String> str = FACTORY->NewStringFromAscii(vector_message);
1756     SetElementNonStrict(result, len, str);
1757   }
1758   return result;
1759 }
1760
1761
1762 LiveEditFunctionTracker::LiveEditFunctionTracker(Isolate* isolate,
1763                                                  FunctionLiteral* fun)
1764     : isolate_(isolate) {
1765   if (isolate_->active_function_info_listener() != NULL) {
1766     isolate_->active_function_info_listener()->FunctionStarted(fun);
1767   }
1768 }
1769
1770
1771 LiveEditFunctionTracker::~LiveEditFunctionTracker() {
1772   if (isolate_->active_function_info_listener() != NULL) {
1773     isolate_->active_function_info_listener()->FunctionDone();
1774   }
1775 }
1776
1777
1778 void LiveEditFunctionTracker::RecordFunctionInfo(
1779     Handle<SharedFunctionInfo> info, FunctionLiteral* lit) {
1780   if (isolate_->active_function_info_listener() != NULL) {
1781     isolate_->active_function_info_listener()->FunctionInfo(info, lit->scope());
1782   }
1783 }
1784
1785
1786 void LiveEditFunctionTracker::RecordRootFunctionInfo(Handle<Code> code) {
1787   isolate_->active_function_info_listener()->FunctionCode(code);
1788 }
1789
1790
1791 bool LiveEditFunctionTracker::IsActive(Isolate* isolate) {
1792   return isolate->active_function_info_listener() != NULL;
1793 }
1794
1795
1796 #else  // ENABLE_DEBUGGER_SUPPORT
1797
1798 // This ifdef-else-endif section provides working or stub implementation of
1799 // LiveEditFunctionTracker.
1800 LiveEditFunctionTracker::LiveEditFunctionTracker(Isolate* isolate,
1801                                                  FunctionLiteral* fun) {
1802 }
1803
1804
1805 LiveEditFunctionTracker::~LiveEditFunctionTracker() {
1806 }
1807
1808
1809 void LiveEditFunctionTracker::RecordFunctionInfo(
1810     Handle<SharedFunctionInfo> info, FunctionLiteral* lit) {
1811 }
1812
1813
1814 void LiveEditFunctionTracker::RecordRootFunctionInfo(Handle<Code> code) {
1815 }
1816
1817
1818 bool LiveEditFunctionTracker::IsActive(Isolate* isolate) {
1819   return false;
1820 }
1821
1822 #endif  // ENABLE_DEBUGGER_SUPPORT
1823
1824
1825
1826 } }  // namespace v8::internal