src/v8/src/liveedit.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5
   6 #include "src/v8.h"
   7
   8 #include "src/liveedit.h"
   9
  10 #include "src/code-stubs.h"
  11 #include "src/compilation-cache.h"
  12 #include "src/compiler.h"
  13 #include "src/debug.h"
  14 #include "src/deoptimizer.h"
  15 #include "src/global-handles.h"
  16 #include "src/messages.h"
  17 #include "src/parser.h"
  18 #include "src/scopeinfo.h"
  19 #include "src/scopes.h"
  20 #include "src/v8memory.h"
  21
  22 namespace v8 {
  23 namespace internal {
  24
  25 void SetElementSloppy(Handle<JSObject> object,
  26                       uint32_t index,
  27                       Handle<Object> value) {
  28   // Ignore return value from SetElement. It can only be a failure if there
  29   // are element setters causing exceptions and the debugger context has none
  30   // of these.
  31   JSObject::SetElement(object, index, value, NONE, SLOPPY).Assert();
  32 }
  33
  34
  35 // A simple implementation of dynamic programming algorithm. It solves
  36 // the problem of finding the difference of 2 arrays. It uses a table of results
  37 // of subproblems. Each cell contains a number together with 2-bit flag
  38 // that helps building the chunk list.
  39 class Differencer {
  40  public:
  41   explicit Differencer(Comparator::Input* input)
  42       : input_(input), len1_(input->GetLength1()), len2_(input->GetLength2()) {
  43     buffer_ = NewArray<int>(len1_ * len2_);
  44   }
  45   ~Differencer() {
  46     DeleteArray(buffer_);
  47   }
  48
  49   void Initialize() {
  50     int array_size = len1_ * len2_;
  51     for (int i = 0; i < array_size; i++) {
  52       buffer_[i] = kEmptyCellValue;
  53     }
  54   }
  55
  56   // Makes sure that result for the full problem is calculated and stored
  57   // in the table together with flags showing a path through subproblems.
  58   void FillTable() {
  59     CompareUpToTail(0, 0);
  60   }
  61
  62   void SaveResult(Comparator::Output* chunk_writer) {
  63     ResultWriter writer(chunk_writer);
  64
  65     int pos1 = 0;
  66     int pos2 = 0;
  67     while (true) {
  68       if (pos1 < len1_) {
  69         if (pos2 < len2_) {
  70           Direction dir = get_direction(pos1, pos2);
  71           switch (dir) {
  72             case EQ:
  73               writer.eq();
  74               pos1++;
  75               pos2++;
  76               break;
  77             case SKIP1:
  78               writer.skip1(1);
  79               pos1++;
  80               break;
  81             case SKIP2:
  82             case SKIP_ANY:
  83               writer.skip2(1);
  84               pos2++;
  85               break;
  86             default:
  87               UNREACHABLE();
  88           }
  89         } else {
  90           writer.skip1(len1_ - pos1);
  91           break;
  92         }
  93       } else {
  94         if (len2_ != pos2) {
  95           writer.skip2(len2_ - pos2);
  96         }
  97         break;
  98       }
  99     }
 100     writer.close();
 101   }
 102
 103  private:
 104   Comparator::Input* input_;
 105   int* buffer_;
 106   int len1_;
 107   int len2_;
 108
 109   enum Direction {
 110     EQ = 0,
 111     SKIP1,
 112     SKIP2,
 113     SKIP_ANY,
 114
 115     MAX_DIRECTION_FLAG_VALUE = SKIP_ANY
 116   };
 117
 118   // Computes result for a subtask and optionally caches it in the buffer table.
 119   // All results values are shifted to make space for flags in the lower bits.
 120   int CompareUpToTail(int pos1, int pos2) {
 121     if (pos1 < len1_) {
 122       if (pos2 < len2_) {
 123         int cached_res = get_value4(pos1, pos2);
 124         if (cached_res == kEmptyCellValue) {
 125           Direction dir;
 126           int res;
 127           if (input_->Equals(pos1, pos2)) {
 128             res = CompareUpToTail(pos1 + 1, pos2 + 1);
 129             dir = EQ;
 130           } else {
 131             int res1 = CompareUpToTail(pos1 + 1, pos2) +
 132                 (1 << kDirectionSizeBits);
 133             int res2 = CompareUpToTail(pos1, pos2 + 1) +
 134                 (1 << kDirectionSizeBits);
 135             if (res1 == res2) {
 136               res = res1;
 137               dir = SKIP_ANY;
 138             } else if (res1 < res2) {
 139               res = res1;
 140               dir = SKIP1;
 141             } else {
 142               res = res2;
 143               dir = SKIP2;
 144             }
 145           }
 146           set_value4_and_dir(pos1, pos2, res, dir);
 147           cached_res = res;
 148         }
 149         return cached_res;
 150       } else {
 151         return (len1_ - pos1) << kDirectionSizeBits;
 152       }
 153     } else {
 154       return (len2_ - pos2) << kDirectionSizeBits;
 155     }
 156   }
 157
 158   inline int& get_cell(int i1, int i2) {
 159     return buffer_[i1 + i2 * len1_];
 160   }
 161
 162   // Each cell keeps a value plus direction. Value is multiplied by 4.
 163   void set_value4_and_dir(int i1, int i2, int value4, Direction dir) {
 164     DCHECK((value4 & kDirectionMask) == 0);
 165     get_cell(i1, i2) = value4 | dir;
 166   }
 167
 168   int get_value4(int i1, int i2) {
 169     return get_cell(i1, i2) & (kMaxUInt32 ^ kDirectionMask);
 170   }
 171   Direction get_direction(int i1, int i2) {
 172     return static_cast<Direction>(get_cell(i1, i2) & kDirectionMask);
 173   }
 174
 175   static const int kDirectionSizeBits = 2;
 176   static const int kDirectionMask = (1 << kDirectionSizeBits) - 1;
 177   static const int kEmptyCellValue = ~0u << kDirectionSizeBits;
 178
 179   // This method only holds static assert statement (unfortunately you cannot
 180   // place one in class scope).
 181   void StaticAssertHolder() {
 182     STATIC_ASSERT(MAX_DIRECTION_FLAG_VALUE < (1 << kDirectionSizeBits));
 183   }
 184
 185   class ResultWriter {
 186    public:
 187     explicit ResultWriter(Comparator::Output* chunk_writer)
 188         : chunk_writer_(chunk_writer), pos1_(0), pos2_(0),
 189           pos1_begin_(-1), pos2_begin_(-1), has_open_chunk_(false) {
 190     }
 191     void eq() {
 192       FlushChunk();
 193       pos1_++;
 194       pos2_++;
 195     }
 196     void skip1(int len1) {
 197       StartChunk();
 198       pos1_ += len1;
 199     }
 200     void skip2(int len2) {
 201       StartChunk();
 202       pos2_ += len2;
 203     }
 204     void close() {
 205       FlushChunk();
 206     }
 207
 208    private:
 209     Comparator::Output* chunk_writer_;
 210     int pos1_;
 211     int pos2_;
 212     int pos1_begin_;
 213     int pos2_begin_;
 214     bool has_open_chunk_;
 215
 216     void StartChunk() {
 217       if (!has_open_chunk_) {
 218         pos1_begin_ = pos1_;
 219         pos2_begin_ = pos2_;
 220         has_open_chunk_ = true;
 221       }
 222     }
 223
 224     void FlushChunk() {
 225       if (has_open_chunk_) {
 226         chunk_writer_->AddChunk(pos1_begin_, pos2_begin_,
 227                                 pos1_ - pos1_begin_, pos2_ - pos2_begin_);
 228         has_open_chunk_ = false;
 229       }
 230     }
 231   };
 232 };
 233
 234
 235 void Comparator::CalculateDifference(Comparator::Input* input,
 236                                      Comparator::Output* result_writer) {
 237   Differencer differencer(input);
 238   differencer.Initialize();
 239   differencer.FillTable();
 240   differencer.SaveResult(result_writer);
 241 }
 242
 243
 244 static bool CompareSubstrings(Handle<String> s1, int pos1,
 245                               Handle<String> s2, int pos2, int len) {
 246   for (int i = 0; i < len; i++) {
 247     if (s1->Get(i + pos1) != s2->Get(i + pos2)) {
 248       return false;
 249     }
 250   }
 251   return true;
 252 }
 253
 254
 255 // Additional to Input interface. Lets switch Input range to subrange.
 256 // More elegant way would be to wrap one Input as another Input object
 257 // and translate positions there, but that would cost us additional virtual
 258 // call per comparison.
 259 class SubrangableInput : public Comparator::Input {
 260  public:
 261   virtual void SetSubrange1(int offset, int len) = 0;
 262   virtual void SetSubrange2(int offset, int len) = 0;
 263 };
 264
 265
 266 class SubrangableOutput : public Comparator::Output {
 267  public:
 268   virtual void SetSubrange1(int offset, int len) = 0;
 269   virtual void SetSubrange2(int offset, int len) = 0;
 270 };
 271
 272
 273 static int min(int a, int b) {
 274   return a < b ? a : b;
 275 }
 276
 277
 278 // Finds common prefix and suffix in input. This parts shouldn't take space in
 279 // linear programming table. Enable subranging in input and output.
 280 static void NarrowDownInput(SubrangableInput* input,
 281     SubrangableOutput* output) {
 282   const int len1 = input->GetLength1();
 283   const int len2 = input->GetLength2();
 284
 285   int common_prefix_len;
 286   int common_suffix_len;
 287
 288   {
 289     common_prefix_len = 0;
 290     int prefix_limit = min(len1, len2);
 291     while (common_prefix_len < prefix_limit &&
 292         input->Equals(common_prefix_len, common_prefix_len)) {
 293       common_prefix_len++;
 294     }
 295
 296     common_suffix_len = 0;
 297     int suffix_limit = min(len1 - common_prefix_len, len2 - common_prefix_len);
 298
 299     while (common_suffix_len < suffix_limit &&
 300         input->Equals(len1 - common_suffix_len - 1,
 301         len2 - common_suffix_len - 1)) {
 302       common_suffix_len++;
 303     }
 304   }
 305
 306   if (common_prefix_len > 0 || common_suffix_len > 0) {
 307     int new_len1 = len1 - common_suffix_len - common_prefix_len;
 308     int new_len2 = len2 - common_suffix_len - common_prefix_len;
 309
 310     input->SetSubrange1(common_prefix_len, new_len1);
 311     input->SetSubrange2(common_prefix_len, new_len2);
 312
 313     output->SetSubrange1(common_prefix_len, new_len1);
 314     output->SetSubrange2(common_prefix_len, new_len2);
 315   }
 316 }
 317
 318
 319 // A helper class that writes chunk numbers into JSArray.
 320 // Each chunk is stored as 3 array elements: (pos1_begin, pos1_end, pos2_end).
 321 class CompareOutputArrayWriter {
 322  public:
 323   explicit CompareOutputArrayWriter(Isolate* isolate)
 324       : array_(isolate->factory()->NewJSArray(10)), current_size_(0) {}
 325
 326   Handle<JSArray> GetResult() {
 327     return array_;
 328   }
 329
 330   void WriteChunk(int char_pos1, int char_pos2, int char_len1, int char_len2) {
 331     Isolate* isolate = array_->GetIsolate();
 332     SetElementSloppy(array_,
 333                      current_size_,
 334                      Handle<Object>(Smi::FromInt(char_pos1), isolate));
 335     SetElementSloppy(array_,
 336                      current_size_ + 1,
 337                      Handle<Object>(Smi::FromInt(char_pos1 + char_len1),
 338                                     isolate));
 339     SetElementSloppy(array_,
 340                      current_size_ + 2,
 341                      Handle<Object>(Smi::FromInt(char_pos2 + char_len2),
 342                                     isolate));
 343     current_size_ += 3;
 344   }
 345
 346  private:
 347   Handle<JSArray> array_;
 348   int current_size_;
 349 };
 350
 351
 352 // Represents 2 strings as 2 arrays of tokens.
 353 // TODO(LiveEdit): Currently it's actually an array of charactres.
 354 //     Make array of tokens instead.
 355 class TokensCompareInput : public Comparator::Input {
 356  public:
 357   TokensCompareInput(Handle<String> s1, int offset1, int len1,
 358                        Handle<String> s2, int offset2, int len2)
 359       : s1_(s1), offset1_(offset1), len1_(len1),
 360         s2_(s2), offset2_(offset2), len2_(len2) {
 361   }
 362   virtual int GetLength1() {
 363     return len1_;
 364   }
 365   virtual int GetLength2() {
 366     return len2_;
 367   }
 368   bool Equals(int index1, int index2) {
 369     return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
 370   }
 371
 372  private:
 373   Handle<String> s1_;
 374   int offset1_;
 375   int len1_;
 376   Handle<String> s2_;
 377   int offset2_;
 378   int len2_;
 379 };
 380
 381
 382 // Stores compare result in JSArray. Converts substring positions
 383 // to absolute positions.
 384 class TokensCompareOutput : public Comparator::Output {
 385  public:
 386   TokensCompareOutput(CompareOutputArrayWriter* array_writer,
 387                       int offset1, int offset2)
 388         : array_writer_(array_writer), offset1_(offset1), offset2_(offset2) {
 389   }
 390
 391   void AddChunk(int pos1, int pos2, int len1, int len2) {
 392     array_writer_->WriteChunk(pos1 + offset1_, pos2 + offset2_, len1, len2);
 393   }
 394
 395  private:
 396   CompareOutputArrayWriter* array_writer_;
 397   int offset1_;
 398   int offset2_;
 399 };
 400
 401
 402 // Wraps raw n-elements line_ends array as a list of n+1 lines. The last line
 403 // never has terminating new line character.
 404 class LineEndsWrapper {
 405  public:
 406   explicit LineEndsWrapper(Handle<String> string)
 407       : ends_array_(String::CalculateLineEnds(string, false)),
 408         string_len_(string->length()) {
 409   }
 410   int length() {
 411     return ends_array_->length() + 1;
 412   }
 413   // Returns start for any line including start of the imaginary line after
 414   // the last line.
 415   int GetLineStart(int index) {
 416     if (index == 0) {
 417       return 0;
 418     } else {
 419       return GetLineEnd(index - 1);
 420     }
 421   }
 422   int GetLineEnd(int index) {
 423     if (index == ends_array_->length()) {
 424       // End of the last line is always an end of the whole string.
 425       // If the string ends with a new line character, the last line is an
 426       // empty string after this character.
 427       return string_len_;
 428     } else {
 429       return GetPosAfterNewLine(index);
 430     }
 431   }
 432
 433  private:
 434   Handle<FixedArray> ends_array_;
 435   int string_len_;
 436
 437   int GetPosAfterNewLine(int index) {
 438     return Smi::cast(ends_array_->get(index))->value() + 1;
 439   }
 440 };
 441
 442
 443 // Represents 2 strings as 2 arrays of lines.
 444 class LineArrayCompareInput : public SubrangableInput {
 445  public:
 446   LineArrayCompareInput(Handle<String> s1, Handle<String> s2,
 447                         LineEndsWrapper line_ends1, LineEndsWrapper line_ends2)
 448       : s1_(s1), s2_(s2), line_ends1_(line_ends1),
 449         line_ends2_(line_ends2),
 450         subrange_offset1_(0), subrange_offset2_(0),
 451         subrange_len1_(line_ends1_.length()),
 452         subrange_len2_(line_ends2_.length()) {
 453   }
 454   int GetLength1() {
 455     return subrange_len1_;
 456   }
 457   int GetLength2() {
 458     return subrange_len2_;
 459   }
 460   bool Equals(int index1, int index2) {
 461     index1 += subrange_offset1_;
 462     index2 += subrange_offset2_;
 463
 464     int line_start1 = line_ends1_.GetLineStart(index1);
 465     int line_start2 = line_ends2_.GetLineStart(index2);
 466     int line_end1 = line_ends1_.GetLineEnd(index1);
 467     int line_end2 = line_ends2_.GetLineEnd(index2);
 468     int len1 = line_end1 - line_start1;
 469     int len2 = line_end2 - line_start2;
 470     if (len1 != len2) {
 471       return false;
 472     }
 473     return CompareSubstrings(s1_, line_start1, s2_, line_start2,
 474                              len1);
 475   }
 476   void SetSubrange1(int offset, int len) {
 477     subrange_offset1_ = offset;
 478     subrange_len1_ = len;
 479   }
 480   void SetSubrange2(int offset, int len) {
 481     subrange_offset2_ = offset;
 482     subrange_len2_ = len;
 483   }
 484
 485  private:
 486   Handle<String> s1_;
 487   Handle<String> s2_;
 488   LineEndsWrapper line_ends1_;
 489   LineEndsWrapper line_ends2_;
 490   int subrange_offset1_;
 491   int subrange_offset2_;
 492   int subrange_len1_;
 493   int subrange_len2_;
 494 };
 495
 496
 497 // Stores compare result in JSArray. For each chunk tries to conduct
 498 // a fine-grained nested diff token-wise.
 499 class TokenizingLineArrayCompareOutput : public SubrangableOutput {
 500  public:
 501   TokenizingLineArrayCompareOutput(LineEndsWrapper line_ends1,
 502                                    LineEndsWrapper line_ends2,
 503                                    Handle<String> s1, Handle<String> s2)
 504       : array_writer_(s1->GetIsolate()),
 505         line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2),
 506         subrange_offset1_(0), subrange_offset2_(0) {
 507   }
 508
 509   void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) {
 510     line_pos1 += subrange_offset1_;
 511     line_pos2 += subrange_offset2_;
 512
 513     int char_pos1 = line_ends1_.GetLineStart(line_pos1);
 514     int char_pos2 = line_ends2_.GetLineStart(line_pos2);
 515     int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1;
 516     int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) - char_pos2;
 517
 518     if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
 519       // Chunk is small enough to conduct a nested token-level diff.
 520       HandleScope subTaskScope(s1_->GetIsolate());
 521
 522       TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
 523                                       s2_, char_pos2, char_len2);
 524       TokensCompareOutput tokens_output(&array_writer_, char_pos1,
 525                                           char_pos2);
 526
 527       Comparator::CalculateDifference(&tokens_input, &tokens_output);
 528     } else {
 529       array_writer_.WriteChunk(char_pos1, char_pos2, char_len1, char_len2);
 530     }
 531   }
 532   void SetSubrange1(int offset, int len) {
 533     subrange_offset1_ = offset;
 534   }
 535   void SetSubrange2(int offset, int len) {
 536     subrange_offset2_ = offset;
 537   }
 538
 539   Handle<JSArray> GetResult() {
 540     return array_writer_.GetResult();
 541   }
 542
 543  private:
 544   static const int CHUNK_LEN_LIMIT = 800;
 545
 546   CompareOutputArrayWriter array_writer_;
 547   LineEndsWrapper line_ends1_;
 548   LineEndsWrapper line_ends2_;
 549   Handle<String> s1_;
 550   Handle<String> s2_;
 551   int subrange_offset1_;
 552   int subrange_offset2_;
 553 };
 554
 555
 556 Handle<JSArray> LiveEdit::CompareStrings(Handle<String> s1,
 557                                          Handle<String> s2) {
 558   s1 = String::Flatten(s1);
 559   s2 = String::Flatten(s2);
 560
 561   LineEndsWrapper line_ends1(s1);
 562   LineEndsWrapper line_ends2(s2);
 563
 564   LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
 565   TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2);
 566
 567   NarrowDownInput(&input, &output);
 568
 569   Comparator::CalculateDifference(&input, &output);
 570
 571   return output.GetResult();
 572 }
 573
 574
 575 // Unwraps JSValue object, returning its field "value"
 576 static Handle<Object> UnwrapJSValue(Handle<JSValue> jsValue) {
 577   return Handle<Object>(jsValue->value(), jsValue->GetIsolate());
 578 }
 579
 580
 581 // Wraps any object into a OpaqueReference, that will hide the object
 582 // from JavaScript.
 583 static Handle<JSValue> WrapInJSValue(Handle<HeapObject> object) {
 584   Isolate* isolate = object->GetIsolate();
 585   Handle<JSFunction> constructor = isolate->opaque_reference_function();
 586   Handle<JSValue> result =
 587       Handle<JSValue>::cast(isolate->factory()->NewJSObject(constructor));
 588   result->set_value(*object);
 589   return result;
 590 }
 591
 592
 593 static Handle<SharedFunctionInfo> UnwrapSharedFunctionInfoFromJSValue(
 594     Handle<JSValue> jsValue) {
 595   Object* shared = jsValue->value();
 596   CHECK(shared->IsSharedFunctionInfo());
 597   return Handle<SharedFunctionInfo>(SharedFunctionInfo::cast(shared));
 598 }
 599
 600
 601 static int GetArrayLength(Handle<JSArray> array) {
 602   Object* length = array->length();
 603   CHECK(length->IsSmi());
 604   return Smi::cast(length)->value();
 605 }
 606
 607
 608 void FunctionInfoWrapper::SetInitialProperties(Handle<String> name,
 609                                                int start_position,
 610                                                int end_position,
 611                                                int param_num,
 612                                                int literal_count,
 613                                                int slot_count,
 614                                                int parent_index) {
 615   HandleScope scope(isolate());
 616   this->SetField(kFunctionNameOffset_, name);
 617   this->SetSmiValueField(kStartPositionOffset_, start_position);
 618   this->SetSmiValueField(kEndPositionOffset_, end_position);
 619   this->SetSmiValueField(kParamNumOffset_, param_num);
 620   this->SetSmiValueField(kLiteralNumOffset_, literal_count);
 621   this->SetSmiValueField(kSlotNumOffset_, slot_count);
 622   this->SetSmiValueField(kParentIndexOffset_, parent_index);
 623 }
 624
 625
 626 void FunctionInfoWrapper::SetFunctionCode(Handle<Code> function_code,
 627                                           Handle<HeapObject> code_scope_info) {
 628   Handle<JSValue> code_wrapper = WrapInJSValue(function_code);
 629   this->SetField(kCodeOffset_, code_wrapper);
 630
 631   Handle<JSValue> scope_wrapper = WrapInJSValue(code_scope_info);
 632   this->SetField(kCodeScopeInfoOffset_, scope_wrapper);
 633 }
 634
 635
 636 void FunctionInfoWrapper::SetSharedFunctionInfo(
 637     Handle<SharedFunctionInfo> info) {
 638   Handle<JSValue> info_holder = WrapInJSValue(info);
 639   this->SetField(kSharedFunctionInfoOffset_, info_holder);
 640 }
 641
 642
 643 Handle<Code> FunctionInfoWrapper::GetFunctionCode() {
 644   Handle<Object> element = this->GetField(kCodeOffset_);
 645   Handle<JSValue> value_wrapper = Handle<JSValue>::cast(element);
 646   Handle<Object> raw_result = UnwrapJSValue(value_wrapper);
 647   CHECK(raw_result->IsCode());
 648   return Handle<Code>::cast(raw_result);
 649 }
 650
 651
 652 Handle<TypeFeedbackVector> FunctionInfoWrapper::GetFeedbackVector() {
 653   Handle<Object> element = this->GetField(kSharedFunctionInfoOffset_);
 654   Handle<TypeFeedbackVector> result;
 655   if (element->IsJSValue()) {
 656     Handle<JSValue> value_wrapper = Handle<JSValue>::cast(element);
 657     Handle<Object> raw_result = UnwrapJSValue(value_wrapper);
 658     Handle<SharedFunctionInfo> shared =
 659         Handle<SharedFunctionInfo>::cast(raw_result);
 660     result = Handle<TypeFeedbackVector>(shared->feedback_vector(), isolate());
 661     CHECK_EQ(result->length(), GetSlotCount());
 662   } else {
 663     // Scripts may never have a SharedFunctionInfo created, so
 664     // create a type feedback vector here.
 665     int slot_count = GetSlotCount();
 666     result = isolate()->factory()->NewTypeFeedbackVector(slot_count);
 667   }
 668   return result;
 669 }
 670
 671
 672 Handle<Object> FunctionInfoWrapper::GetCodeScopeInfo() {
 673   Handle<Object> element = this->GetField(kCodeScopeInfoOffset_);
 674   return UnwrapJSValue(Handle<JSValue>::cast(element));
 675 }
 676
 677
 678 void SharedInfoWrapper::SetProperties(Handle<String> name,
 679                                       int start_position,
 680                                       int end_position,
 681                                       Handle<SharedFunctionInfo> info) {
 682   HandleScope scope(isolate());
 683   this->SetField(kFunctionNameOffset_, name);
 684   Handle<JSValue> info_holder = WrapInJSValue(info);
 685   this->SetField(kSharedInfoOffset_, info_holder);
 686   this->SetSmiValueField(kStartPositionOffset_, start_position);
 687   this->SetSmiValueField(kEndPositionOffset_, end_position);
 688 }
 689
 690
 691 Handle<SharedFunctionInfo> SharedInfoWrapper::GetInfo() {
 692   Handle<Object> element = this->GetField(kSharedInfoOffset_);
 693   Handle<JSValue> value_wrapper = Handle<JSValue>::cast(element);
 694   return UnwrapSharedFunctionInfoFromJSValue(value_wrapper);
 695 }
 696
 697
 698 class FunctionInfoListener {
 699  public:
 700   explicit FunctionInfoListener(Isolate* isolate) {
 701     current_parent_index_ = -1;
 702     len_ = 0;
 703     result_ = isolate->factory()->NewJSArray(10);
 704   }
 705
 706   void FunctionStarted(FunctionLiteral* fun) {
 707     HandleScope scope(isolate());
 708     FunctionInfoWrapper info = FunctionInfoWrapper::Create(isolate());
 709     info.SetInitialProperties(fun->name(), fun->start_position(),
 710                               fun->end_position(), fun->parameter_count(),
 711                               fun->materialized_literal_count(),
 712                               fun->slot_count(),
 713                               current_parent_index_);
 714     current_parent_index_ = len_;
 715     SetElementSloppy(result_, len_, info.GetJSArray());
 716     len_++;
 717   }
 718
 719   void FunctionDone() {
 720     HandleScope scope(isolate());
 721     FunctionInfoWrapper info =
 722         FunctionInfoWrapper::cast(
 723             *Object::GetElement(
 724                 isolate(), result_, current_parent_index_).ToHandleChecked());
 725     current_parent_index_ = info.GetParentIndex();
 726   }
 727
 728   // Saves only function code, because for a script function we
 729   // may never create a SharedFunctionInfo object.
 730   void FunctionCode(Handle<Code> function_code) {
 731     FunctionInfoWrapper info =
 732         FunctionInfoWrapper::cast(
 733             *Object::GetElement(
 734                 isolate(), result_, current_parent_index_).ToHandleChecked());
 735     info.SetFunctionCode(function_code,
 736                          Handle<HeapObject>(isolate()->heap()->null_value()));
 737   }
 738
 739   // Saves full information about a function: its code, its scope info
 740   // and a SharedFunctionInfo object.
 741   void FunctionInfo(Handle<SharedFunctionInfo> shared, Scope* scope,
 742                     Zone* zone) {
 743     if (!shared->IsSharedFunctionInfo()) {
 744       return;
 745     }
 746     FunctionInfoWrapper info =
 747         FunctionInfoWrapper::cast(
 748             *Object::GetElement(
 749                 isolate(), result_, current_parent_index_).ToHandleChecked());
 750     info.SetFunctionCode(Handle<Code>(shared->code()),
 751                          Handle<HeapObject>(shared->scope_info()));
 752     info.SetSharedFunctionInfo(shared);
 753
 754     Handle<Object> scope_info_list = SerializeFunctionScope(scope, zone);
 755     info.SetFunctionScopeInfo(scope_info_list);
 756   }
 757
 758   Handle<JSArray> GetResult() { return result_; }
 759
 760  private:
 761   Isolate* isolate() const { return result_->GetIsolate(); }
 762
 763   Handle<Object> SerializeFunctionScope(Scope* scope, Zone* zone) {
 764     Handle<JSArray> scope_info_list = isolate()->factory()->NewJSArray(10);
 765     int scope_info_length = 0;
 766
 767     // Saves some description of scope. It stores name and indexes of
 768     // variables in the whole scope chain. Null-named slots delimit
 769     // scopes of this chain.
 770     Scope* current_scope = scope;
 771     while (current_scope != NULL) {
 772       HandleScope handle_scope(isolate());
 773       ZoneList<Variable*> stack_list(current_scope->StackLocalCount(), zone);
 774       ZoneList<Variable*> context_list(
 775           current_scope->ContextLocalCount(), zone);
 776       current_scope->CollectStackAndContextLocals(&stack_list, &context_list);
 777       context_list.Sort(&Variable::CompareIndex);
 778
 779       for (int i = 0; i < context_list.length(); i++) {
 780         SetElementSloppy(scope_info_list,
 781                          scope_info_length,
 782                          context_list[i]->name());
 783         scope_info_length++;
 784         SetElementSloppy(
 785             scope_info_list,
 786             scope_info_length,
 787             Handle<Smi>(Smi::FromInt(context_list[i]->index()), isolate()));
 788         scope_info_length++;
 789       }
 790       SetElementSloppy(scope_info_list,
 791                        scope_info_length,
 792                        Handle<Object>(isolate()->heap()->null_value(),
 793                                       isolate()));
 794       scope_info_length++;
 795
 796       current_scope = current_scope->outer_scope();
 797     }
 798
 799     return scope_info_list;
 800   }
 801
 802   Handle<JSArray> result_;
 803   int len_;
 804   int current_parent_index_;
 805 };
 806
 807
 808 void LiveEdit::InitializeThreadLocal(Debug* debug) {
 809   debug->thread_local_.frame_drop_mode_ = LiveEdit::FRAMES_UNTOUCHED;
 810 }
 811
 812
 813 bool LiveEdit::SetAfterBreakTarget(Debug* debug) {
 814   Code* code = NULL;
 815   Isolate* isolate = debug->isolate_;
 816   switch (debug->thread_local_.frame_drop_mode_) {
 817     case FRAMES_UNTOUCHED:
 818       return false;
 819     case FRAME_DROPPED_IN_IC_CALL:
 820       // We must have been calling IC stub. Do not go there anymore.
 821       code = isolate->builtins()->builtin(Builtins::kPlainReturn_LiveEdit);
 822       break;
 823     case FRAME_DROPPED_IN_DEBUG_SLOT_CALL:
 824       // Debug break slot stub does not return normally, instead it manually
 825       // cleans the stack and jumps. We should patch the jump address.
 826       code = isolate->builtins()->builtin(Builtins::kFrameDropper_LiveEdit);
 827       break;
 828     case FRAME_DROPPED_IN_DIRECT_CALL:
 829       // Nothing to do, after_break_target is not used here.
 830       return true;
 831     case FRAME_DROPPED_IN_RETURN_CALL:
 832       code = isolate->builtins()->builtin(Builtins::kFrameDropper_LiveEdit);
 833       break;
 834     case CURRENTLY_SET_MODE:
 835       UNREACHABLE();
 836       break;
 837   }
 838   debug->after_break_target_ = code->entry();
 839   return true;
 840 }
 841
 842
 843 MaybeHandle<JSArray> LiveEdit::GatherCompileInfo(Handle<Script> script,
 844                                                  Handle<String> source) {
 845   Isolate* isolate = script->GetIsolate();
 846
 847   FunctionInfoListener listener(isolate);
 848   Handle<Object> original_source =
 849       Handle<Object>(script->source(), isolate);
 850   script->set_source(*source);
 851   isolate->set_active_function_info_listener(&listener);
 852
 853   {
 854     // Creating verbose TryCatch from public API is currently the only way to
 855     // force code save location. We do not use this the object directly.
 856     v8::TryCatch try_catch;
 857     try_catch.SetVerbose(true);
 858
 859     // A logical 'try' section.
 860     Compiler::CompileForLiveEdit(script);
 861   }
 862
 863   // A logical 'catch' section.
 864   Handle<JSObject> rethrow_exception;
 865   if (isolate->has_pending_exception()) {
 866     Handle<Object> exception(isolate->pending_exception(), isolate);
 867     MessageLocation message_location = isolate->GetMessageLocation();
 868
 869     isolate->clear_pending_message();
 870     isolate->clear_pending_exception();
 871
 872     // If possible, copy positions from message object to exception object.
 873     if (exception->IsJSObject() && !message_location.script().is_null()) {
 874       rethrow_exception = Handle<JSObject>::cast(exception);
 875
 876       Factory* factory = isolate->factory();
 877       Handle<String> start_pos_key = factory->InternalizeOneByteString(
 878           STATIC_CHAR_VECTOR("startPosition"));
 879       Handle<String> end_pos_key =
 880           factory->InternalizeOneByteString(STATIC_CHAR_VECTOR("endPosition"));
 881       Handle<String> script_obj_key =
 882           factory->InternalizeOneByteString(STATIC_CHAR_VECTOR("scriptObject"));
 883       Handle<Smi> start_pos(
 884           Smi::FromInt(message_location.start_pos()), isolate);
 885       Handle<Smi> end_pos(Smi::FromInt(message_location.end_pos()), isolate);
 886       Handle<JSObject> script_obj =
 887           Script::GetWrapper(message_location.script());
 888       Object::SetProperty(rethrow_exception, start_pos_key, start_pos, SLOPPY)
 889           .Assert();
 890       Object::SetProperty(rethrow_exception, end_pos_key, end_pos, SLOPPY)
 891           .Assert();
 892       Object::SetProperty(rethrow_exception, script_obj_key, script_obj, SLOPPY)
 893           .Assert();
 894     }
 895   }
 896
 897   // A logical 'finally' section.
 898   isolate->set_active_function_info_listener(NULL);
 899   script->set_source(*original_source);
 900
 901   if (rethrow_exception.is_null()) {
 902     return listener.GetResult();
 903   } else {
 904     return isolate->Throw<JSArray>(rethrow_exception);
 905   }
 906 }
 907
 908
 909 void LiveEdit::WrapSharedFunctionInfos(Handle<JSArray> array) {
 910   Isolate* isolate = array->GetIsolate();
 911   HandleScope scope(isolate);
 912   int len = GetArrayLength(array);
 913   for (int i = 0; i < len; i++) {
 914     Handle<SharedFunctionInfo> info(
 915         SharedFunctionInfo::cast(
 916             *Object::GetElement(isolate, array, i).ToHandleChecked()));
 917     SharedInfoWrapper info_wrapper = SharedInfoWrapper::Create(isolate);
 918     Handle<String> name_handle(String::cast(info->name()));
 919     info_wrapper.SetProperties(name_handle, info->start_position(),
 920                                info->end_position(), info);
 921     SetElementSloppy(array, i, info_wrapper.GetJSArray());
 922   }
 923 }
 924
 925
 926 // Visitor that finds all references to a particular code object,
 927 // including "CODE_TARGET" references in other code objects and replaces
 928 // them on the fly.
 929 class ReplacingVisitor : public ObjectVisitor {
 930  public:
 931   explicit ReplacingVisitor(Code* original, Code* substitution)
 932     : original_(original), substitution_(substitution) {
 933   }
 934
 935   virtual void VisitPointers(Object** start, Object** end) {
 936     for (Object** p = start; p < end; p++) {
 937       if (*p == original_) {
 938         *p = substitution_;
 939       }
 940     }
 941   }
 942
 943   virtual void VisitCodeEntry(Address entry) {
 944     if (Code::GetObjectFromEntryAddress(entry) == original_) {
 945       Address substitution_entry = substitution_->instruction_start();
 946       Memory::Address_at(entry) = substitution_entry;
 947     }
 948   }
 949
 950   virtual void VisitCodeTarget(RelocInfo* rinfo) {
 951     if (RelocInfo::IsCodeTarget(rinfo->rmode()) &&
 952         Code::GetCodeFromTargetAddress(rinfo->target_address()) == original_) {
 953       Address substitution_entry = substitution_->instruction_start();
 954       rinfo->set_target_address(substitution_entry);
 955     }
 956   }
 957
 958   virtual void VisitDebugTarget(RelocInfo* rinfo) {
 959     VisitCodeTarget(rinfo);
 960   }
 961
 962  private:
 963   Code* original_;
 964   Code* substitution_;
 965 };
 966
 967
 968 // Finds all references to original and replaces them with substitution.
 969 static void ReplaceCodeObject(Handle<Code> original,
 970                               Handle<Code> substitution) {
 971   // Perform a full GC in order to ensure that we are not in the middle of an
 972   // incremental marking phase when we are replacing the code object.
 973   // Since we are not in an incremental marking phase we can write pointers
 974   // to code objects (that are never in new space) without worrying about
 975   // write barriers.
 976   Heap* heap = original->GetHeap();
 977   HeapIterator iterator(heap);
 978
 979   DCHECK(!heap->InNewSpace(*substitution));
 980
 981   ReplacingVisitor visitor(*original, *substitution);
 982
 983   // Iterate over all roots. Stack frames may have pointer into original code,
 984   // so temporary replace the pointers with offset numbers
 985   // in prologue/epilogue.
 986   heap->IterateRoots(&visitor, VISIT_ALL);
 987
 988   // Now iterate over all pointers of all objects, including code_target
 989   // implicit pointers.
 990   for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
 991     obj->Iterate(&visitor);
 992   }
 993 }
 994
 995
 996 // Patch function literals.
 997 // Name 'literals' is a misnomer. Rather it's a cache for complex object
 998 // boilerplates and for a native context. We must clean cached values.
 999 // Additionally we may need to allocate a new array if number of literals
1000 // changed.
1001 class LiteralFixer {
1002  public:
1003   static void PatchLiterals(FunctionInfoWrapper* compile_info_wrapper,
1004                             Handle<SharedFunctionInfo> shared_info,
1005                             Isolate* isolate) {
1006     int new_literal_count = compile_info_wrapper->GetLiteralCount();
1007     if (new_literal_count > 0) {
1008       new_literal_count += JSFunction::kLiteralsPrefixSize;
1009     }
1010     int old_literal_count = shared_info->num_literals();
1011
1012     if (old_literal_count == new_literal_count) {
1013       // If literal count didn't change, simply go over all functions
1014       // and clear literal arrays.
1015       ClearValuesVisitor visitor;
1016       IterateJSFunctions(shared_info, &visitor);
1017     } else {
1018       // When literal count changes, we have to create new array instances.
1019       // Since we cannot create instances when iterating heap, we should first
1020       // collect all functions and fix their literal arrays.
1021       Handle<FixedArray> function_instances =
1022           CollectJSFunctions(shared_info, isolate);
1023       for (int i = 0; i < function_instances->length(); i++) {
1024         Handle<JSFunction> fun(JSFunction::cast(function_instances->get(i)));
1025         Handle<FixedArray> old_literals(fun->literals());
1026         Handle<FixedArray> new_literals =
1027             isolate->factory()->NewFixedArray(new_literal_count);
1028         if (new_literal_count > 0) {
1029           Handle<Context> native_context;
1030           if (old_literals->length() >
1031               JSFunction::kLiteralNativeContextIndex) {
1032             native_context = Handle<Context>(
1033                 JSFunction::NativeContextFromLiterals(fun->literals()));
1034           } else {
1035             native_context = Handle<Context>(fun->context()->native_context());
1036           }
1037           new_literals->set(JSFunction::kLiteralNativeContextIndex,
1038               *native_context);
1039         }
1040         fun->set_literals(*new_literals);
1041       }
1042
1043       shared_info->set_num_literals(new_literal_count);
1044     }
1045   }
1046
1047  private:
1048   // Iterates all function instances in the HEAP that refers to the
1049   // provided shared_info.
1050   template<typename Visitor>
1051   static void IterateJSFunctions(Handle<SharedFunctionInfo> shared_info,
1052                                  Visitor* visitor) {
1053     HeapIterator iterator(shared_info->GetHeap());
1054     for (HeapObject* obj = iterator.next(); obj != NULL;
1055         obj = iterator.next()) {
1056       if (obj->IsJSFunction()) {
1057         JSFunction* function = JSFunction::cast(obj);
1058         if (function->shared() == *shared_info) {
1059           visitor->visit(function);
1060         }
1061       }
1062     }
1063   }
1064
1065   // Finds all instances of JSFunction that refers to the provided shared_info
1066   // and returns array with them.
1067   static Handle<FixedArray> CollectJSFunctions(
1068       Handle<SharedFunctionInfo> shared_info, Isolate* isolate) {
1069     CountVisitor count_visitor;
1070     count_visitor.count = 0;
1071     IterateJSFunctions(shared_info, &count_visitor);
1072     int size = count_visitor.count;
1073
1074     Handle<FixedArray> result = isolate->factory()->NewFixedArray(size);
1075     if (size > 0) {
1076       CollectVisitor collect_visitor(result);
1077       IterateJSFunctions(shared_info, &collect_visitor);
1078     }
1079     return result;
1080   }
1081
1082   class ClearValuesVisitor {
1083    public:
1084     void visit(JSFunction* fun) {
1085       FixedArray* literals = fun->literals();
1086       int len = literals->length();
1087       for (int j = JSFunction::kLiteralsPrefixSize; j < len; j++) {
1088         literals->set_undefined(j);
1089       }
1090     }
1091   };
1092
1093   class CountVisitor {
1094    public:
1095     void visit(JSFunction* fun) {
1096       count++;
1097     }
1098     int count;
1099   };
1100
1101   class CollectVisitor {
1102    public:
1103     explicit CollectVisitor(Handle<FixedArray> output)
1104         : m_output(output), m_pos(0) {}
1105
1106     void visit(JSFunction* fun) {
1107       m_output->set(m_pos, fun);
1108       m_pos++;
1109     }
1110    private:
1111     Handle<FixedArray> m_output;
1112     int m_pos;
1113   };
1114 };
1115
1116
1117 // Check whether the code is natural function code (not a lazy-compile stub
1118 // code).
1119 static bool IsJSFunctionCode(Code* code) {
1120   return code->kind() == Code::FUNCTION;
1121 }
1122
1123
1124 // Returns true if an instance of candidate were inlined into function's code.
1125 static bool IsInlined(JSFunction* function, SharedFunctionInfo* candidate) {
1126   DisallowHeapAllocation no_gc;
1127
1128   if (function->code()->kind() != Code::OPTIMIZED_FUNCTION) return false;
1129
1130   DeoptimizationInputData* data =
1131       DeoptimizationInputData::cast(function->code()->deoptimization_data());
1132
1133   if (data == function->GetIsolate()->heap()->empty_fixed_array()) {
1134     return false;
1135   }
1136
1137   FixedArray* literals = data->LiteralArray();
1138
1139   int inlined_count = data->InlinedFunctionCount()->value();
1140   for (int i = 0; i < inlined_count; ++i) {
1141     JSFunction* inlined = JSFunction::cast(literals->get(i));
1142     if (inlined->shared() == candidate) return true;
1143   }
1144
1145   return false;
1146 }
1147
1148
1149 // Marks code that shares the same shared function info or has inlined
1150 // code that shares the same function info.
1151 class DependentFunctionMarker: public OptimizedFunctionVisitor {
1152  public:
1153   SharedFunctionInfo* shared_info_;
1154   bool found_;
1155
1156   explicit DependentFunctionMarker(SharedFunctionInfo* shared_info)
1157     : shared_info_(shared_info), found_(false) { }
1158
1159   virtual void EnterContext(Context* context) { }  // Don't care.
1160   virtual void LeaveContext(Context* context)  { }  // Don't care.
1161   virtual void VisitFunction(JSFunction* function) {
1162     // It should be guaranteed by the iterator that everything is optimized.
1163     DCHECK(function->code()->kind() == Code::OPTIMIZED_FUNCTION);
1164     if (shared_info_ == function->shared() ||
1165         IsInlined(function, shared_info_)) {
1166       // Mark the code for deoptimization.
1167       function->code()->set_marked_for_deoptimization(true);
1168       found_ = true;
1169     }
1170   }
1171 };
1172
1173
1174 static void DeoptimizeDependentFunctions(SharedFunctionInfo* function_info) {
1175   DisallowHeapAllocation no_allocation;
1176   DependentFunctionMarker marker(function_info);
1177   // TODO(titzer): need to traverse all optimized code to find OSR code here.
1178   Deoptimizer::VisitAllOptimizedFunctions(function_info->GetIsolate(), &marker);
1179
1180   if (marker.found_) {
1181     // Only go through with the deoptimization if something was found.
1182     Deoptimizer::DeoptimizeMarkedCode(function_info->GetIsolate());
1183   }
1184 }
1185
1186
1187 void LiveEdit::ReplaceFunctionCode(
1188     Handle<JSArray> new_compile_info_array,
1189     Handle<JSArray> shared_info_array) {
1190   Isolate* isolate = new_compile_info_array->GetIsolate();
1191
1192   FunctionInfoWrapper compile_info_wrapper(new_compile_info_array);
1193   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1194
1195   Handle<SharedFunctionInfo> shared_info = shared_info_wrapper.GetInfo();
1196
1197   if (IsJSFunctionCode(shared_info->code())) {
1198     Handle<Code> code = compile_info_wrapper.GetFunctionCode();
1199     ReplaceCodeObject(Handle<Code>(shared_info->code()), code);
1200     Handle<Object> code_scope_info = compile_info_wrapper.GetCodeScopeInfo();
1201     if (code_scope_info->IsFixedArray()) {
1202       shared_info->set_scope_info(ScopeInfo::cast(*code_scope_info));
1203     }
1204     shared_info->DisableOptimization(kLiveEdit);
1205     // Update the type feedback vector
1206     Handle<TypeFeedbackVector> feedback_vector =
1207         compile_info_wrapper.GetFeedbackVector();
1208     shared_info->set_feedback_vector(*feedback_vector);
1209   }
1210
1211   if (shared_info->debug_info()->IsDebugInfo()) {
1212     Handle<DebugInfo> debug_info(DebugInfo::cast(shared_info->debug_info()));
1213     Handle<Code> new_original_code =
1214         isolate->factory()->CopyCode(compile_info_wrapper.GetFunctionCode());
1215     debug_info->set_original_code(*new_original_code);
1216   }
1217
1218   int start_position = compile_info_wrapper.GetStartPosition();
1219   int end_position = compile_info_wrapper.GetEndPosition();
1220   shared_info->set_start_position(start_position);
1221   shared_info->set_end_position(end_position);
1222
1223   LiteralFixer::PatchLiterals(&compile_info_wrapper, shared_info, isolate);
1224
1225   shared_info->set_construct_stub(
1226       isolate->builtins()->builtin(Builtins::kJSConstructStubGeneric));
1227
1228   DeoptimizeDependentFunctions(*shared_info);
1229   isolate->compilation_cache()->Remove(shared_info);
1230 }
1231
1232
1233 void LiveEdit::FunctionSourceUpdated(Handle<JSArray> shared_info_array) {
1234   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1235   Handle<SharedFunctionInfo> shared_info = shared_info_wrapper.GetInfo();
1236
1237   DeoptimizeDependentFunctions(*shared_info);
1238   shared_info_array->GetIsolate()->compilation_cache()->Remove(shared_info);
1239 }
1240
1241
1242 void LiveEdit::SetFunctionScript(Handle<JSValue> function_wrapper,
1243                                  Handle<Object> script_handle) {
1244   Handle<SharedFunctionInfo> shared_info =
1245       UnwrapSharedFunctionInfoFromJSValue(function_wrapper);
1246   CHECK(script_handle->IsScript() || script_handle->IsUndefined());
1247   shared_info->set_script(*script_handle);
1248
1249   function_wrapper->GetIsolate()->compilation_cache()->Remove(shared_info);
1250 }
1251
1252
1253 // For a script text change (defined as position_change_array), translates
1254 // position in unchanged text to position in changed text.
1255 // Text change is a set of non-overlapping regions in text, that have changed
1256 // their contents and length. It is specified as array of groups of 3 numbers:
1257 // (change_begin, change_end, change_end_new_position).
1258 // Each group describes a change in text; groups are sorted by change_begin.
1259 // Only position in text beyond any changes may be successfully translated.
1260 // If a positions is inside some region that changed, result is currently
1261 // undefined.
1262 static int TranslatePosition(int original_position,
1263                              Handle<JSArray> position_change_array) {
1264   int position_diff = 0;
1265   int array_len = GetArrayLength(position_change_array);
1266   Isolate* isolate = position_change_array->GetIsolate();
1267   // TODO(635): binary search may be used here
1268   for (int i = 0; i < array_len; i += 3) {
1269     HandleScope scope(isolate);
1270     Handle<Object> element = Object::GetElement(
1271         isolate, position_change_array, i).ToHandleChecked();
1272     CHECK(element->IsSmi());
1273     int chunk_start = Handle<Smi>::cast(element)->value();
1274     if (original_position < chunk_start) {
1275       break;
1276     }
1277     element = Object::GetElement(
1278         isolate, position_change_array, i + 1).ToHandleChecked();
1279     CHECK(element->IsSmi());
1280     int chunk_end = Handle<Smi>::cast(element)->value();
1281     // Position mustn't be inside a chunk.
1282     DCHECK(original_position >= chunk_end);
1283     element = Object::GetElement(
1284         isolate, position_change_array, i + 2).ToHandleChecked();
1285     CHECK(element->IsSmi());
1286     int chunk_changed_end = Handle<Smi>::cast(element)->value();
1287     position_diff = chunk_changed_end - chunk_end;
1288   }
1289
1290   return original_position + position_diff;
1291 }
1292
1293
1294 // Auto-growing buffer for writing relocation info code section. This buffer
1295 // is a simplified version of buffer from Assembler. Unlike Assembler, this
1296 // class is platform-independent and it works without dealing with instructions.
1297 // As specified by RelocInfo format, the buffer is filled in reversed order:
1298 // from upper to lower addresses.
1299 // It uses NewArray/DeleteArray for memory management.
1300 class RelocInfoBuffer {
1301  public:
1302   RelocInfoBuffer(int buffer_initial_capicity, byte* pc) {
1303     buffer_size_ = buffer_initial_capicity + kBufferGap;
1304     buffer_ = NewArray<byte>(buffer_size_);
1305
1306     reloc_info_writer_.Reposition(buffer_ + buffer_size_, pc);
1307   }
1308   ~RelocInfoBuffer() {
1309     DeleteArray(buffer_);
1310   }
1311
1312   // As specified by RelocInfo format, the buffer is filled in reversed order:
1313   // from upper to lower addresses.
1314   void Write(const RelocInfo* rinfo) {
1315     if (buffer_ + kBufferGap >= reloc_info_writer_.pos()) {
1316       Grow();
1317     }
1318     reloc_info_writer_.Write(rinfo);
1319   }
1320
1321   Vector<byte> GetResult() {
1322     // Return the bytes from pos up to end of buffer.
1323     int result_size =
1324         static_cast<int>((buffer_ + buffer_size_) - reloc_info_writer_.pos());
1325     return Vector<byte>(reloc_info_writer_.pos(), result_size);
1326   }
1327
1328  private:
1329   void Grow() {
1330     // Compute new buffer size.
1331     int new_buffer_size;
1332     if (buffer_size_ < 2 * KB) {
1333       new_buffer_size = 4 * KB;
1334     } else {
1335       new_buffer_size = 2 * buffer_size_;
1336     }
1337     // Some internal data structures overflow for very large buffers,
1338     // they must ensure that kMaximalBufferSize is not too large.
1339     if (new_buffer_size > kMaximalBufferSize) {
1340       V8::FatalProcessOutOfMemory("RelocInfoBuffer::GrowBuffer");
1341     }
1342
1343     // Set up new buffer.
1344     byte* new_buffer = NewArray<byte>(new_buffer_size);
1345
1346     // Copy the data.
1347     int curently_used_size =
1348         static_cast<int>(buffer_ + buffer_size_ - reloc_info_writer_.pos());
1349     MemMove(new_buffer + new_buffer_size - curently_used_size,
1350             reloc_info_writer_.pos(), curently_used_size);
1351
1352     reloc_info_writer_.Reposition(
1353         new_buffer + new_buffer_size - curently_used_size,
1354         reloc_info_writer_.last_pc());
1355
1356     DeleteArray(buffer_);
1357     buffer_ = new_buffer;
1358     buffer_size_ = new_buffer_size;
1359   }
1360
1361   RelocInfoWriter reloc_info_writer_;
1362   byte* buffer_;
1363   int buffer_size_;
1364
1365   static const int kBufferGap = RelocInfoWriter::kMaxSize;
1366   static const int kMaximalBufferSize = 512*MB;
1367 };
1368
1369
1370 // Patch positions in code (changes relocation info section) and possibly
1371 // returns new instance of code.
1372 static Handle<Code> PatchPositionsInCode(
1373     Handle<Code> code,
1374     Handle<JSArray> position_change_array) {
1375   Isolate* isolate = code->GetIsolate();
1376
1377   RelocInfoBuffer buffer_writer(code->relocation_size(),
1378                                 code->instruction_start());
1379
1380   {
1381     for (RelocIterator it(*code); !it.done(); it.next()) {
1382       RelocInfo* rinfo = it.rinfo();
1383       if (RelocInfo::IsPosition(rinfo->rmode())) {
1384         int position = static_cast<int>(rinfo->data());
1385         int new_position = TranslatePosition(position,
1386                                              position_change_array);
1387         if (position != new_position) {
1388           RelocInfo info_copy(rinfo->pc(), rinfo->rmode(), new_position, NULL);
1389           buffer_writer.Write(&info_copy);
1390           continue;
1391         }
1392       }
1393       if (RelocInfo::IsRealRelocMode(rinfo->rmode())) {
1394         buffer_writer.Write(it.rinfo());
1395       }
1396     }
1397   }
1398
1399   Vector<byte> buffer = buffer_writer.GetResult();
1400
1401   if (buffer.length() == code->relocation_size()) {
1402     // Simply patch relocation area of code.
1403     MemCopy(code->relocation_start(), buffer.start(), buffer.length());
1404     return code;
1405   } else {
1406     // Relocation info section now has different size. We cannot simply
1407     // rewrite it inside code object. Instead we have to create a new
1408     // code object.
1409     Handle<Code> result(isolate->factory()->CopyCode(code, buffer));
1410     return result;
1411   }
1412 }
1413
1414
1415 void LiveEdit::PatchFunctionPositions(Handle<JSArray> shared_info_array,
1416                                       Handle<JSArray> position_change_array) {
1417   SharedInfoWrapper shared_info_wrapper(shared_info_array);
1418   Handle<SharedFunctionInfo> info = shared_info_wrapper.GetInfo();
1419
1420   int old_function_start = info->start_position();
1421   int new_function_start = TranslatePosition(old_function_start,
1422                                              position_change_array);
1423   int new_function_end = TranslatePosition(info->end_position(),
1424                                            position_change_array);
1425   int new_function_token_pos =
1426       TranslatePosition(info->function_token_position(), position_change_array);
1427
1428   info->set_start_position(new_function_start);
1429   info->set_end_position(new_function_end);
1430   info->set_function_token_position(new_function_token_pos);
1431
1432   if (IsJSFunctionCode(info->code())) {
1433     // Patch relocation info section of the code.
1434     Handle<Code> patched_code = PatchPositionsInCode(Handle<Code>(info->code()),
1435                                                      position_change_array);
1436     if (*patched_code != info->code()) {
1437       // Replace all references to the code across the heap. In particular,
1438       // some stubs may refer to this code and this code may be being executed
1439       // on stack (it is safe to substitute the code object on stack, because
1440       // we only change the structure of rinfo and leave instructions
1441       // untouched).
1442       ReplaceCodeObject(Handle<Code>(info->code()), patched_code);
1443     }
1444   }
1445 }
1446
1447
1448 static Handle<Script> CreateScriptCopy(Handle<Script> original) {
1449   Isolate* isolate = original->GetIsolate();
1450
1451   Handle<String> original_source(String::cast(original->source()));
1452   Handle<Script> copy = isolate->factory()->NewScript(original_source);
1453
1454   copy->set_name(original->name());
1455   copy->set_line_offset(original->line_offset());
1456   copy->set_column_offset(original->column_offset());
1457   copy->set_type(original->type());
1458   copy->set_context_data(original->context_data());
1459   copy->set_eval_from_shared(original->eval_from_shared());
1460   copy->set_eval_from_instructions_offset(
1461       original->eval_from_instructions_offset());
1462
1463   // Copy all the flags, but clear compilation state.
1464   copy->set_flags(original->flags());
1465   copy->set_compilation_state(Script::COMPILATION_STATE_INITIAL);
1466
1467   return copy;
1468 }
1469
1470
1471 Handle<Object> LiveEdit::ChangeScriptSource(Handle<Script> original_script,
1472                                             Handle<String> new_source,
1473                                             Handle<Object> old_script_name) {
1474   Isolate* isolate = original_script->GetIsolate();
1475   Handle<Object> old_script_object;
1476   if (old_script_name->IsString()) {
1477     Handle<Script> old_script = CreateScriptCopy(original_script);
1478     old_script->set_name(String::cast(*old_script_name));
1479     old_script_object = old_script;
1480     isolate->debug()->OnAfterCompile(old_script);
1481   } else {
1482     old_script_object = isolate->factory()->null_value();
1483   }
1484
1485   original_script->set_source(*new_source);
1486
1487   // Drop line ends so that they will be recalculated.
1488   original_script->set_line_ends(isolate->heap()->undefined_value());
1489
1490   return old_script_object;
1491 }
1492
1493
1494
1495 void LiveEdit::ReplaceRefToNestedFunction(
1496     Handle<JSValue> parent_function_wrapper,
1497     Handle<JSValue> orig_function_wrapper,
1498     Handle<JSValue> subst_function_wrapper) {
1499
1500   Handle<SharedFunctionInfo> parent_shared =
1501       UnwrapSharedFunctionInfoFromJSValue(parent_function_wrapper);
1502   Handle<SharedFunctionInfo> orig_shared =
1503       UnwrapSharedFunctionInfoFromJSValue(orig_function_wrapper);
1504   Handle<SharedFunctionInfo> subst_shared =
1505       UnwrapSharedFunctionInfoFromJSValue(subst_function_wrapper);
1506
1507   for (RelocIterator it(parent_shared->code()); !it.done(); it.next()) {
1508     if (it.rinfo()->rmode() == RelocInfo::EMBEDDED_OBJECT) {
1509       if (it.rinfo()->target_object() == *orig_shared) {
1510         it.rinfo()->set_target_object(*subst_shared);
1511       }
1512     }
1513   }
1514 }
1515
1516
1517 // Check an activation against list of functions. If there is a function
1518 // that matches, its status in result array is changed to status argument value.
1519 static bool CheckActivation(Handle<JSArray> shared_info_array,
1520                             Handle<JSArray> result,
1521                             StackFrame* frame,
1522                             LiveEdit::FunctionPatchabilityStatus status) {
1523   if (!frame->is_java_script()) return false;
1524
1525   Handle<JSFunction> function(JavaScriptFrame::cast(frame)->function());
1526
1527   Isolate* isolate = shared_info_array->GetIsolate();
1528   int len = GetArrayLength(shared_info_array);
1529   for (int i = 0; i < len; i++) {
1530     HandleScope scope(isolate);
1531     Handle<Object> element =
1532         Object::GetElement(isolate, shared_info_array, i).ToHandleChecked();
1533     Handle<JSValue> jsvalue = Handle<JSValue>::cast(element);
1534     Handle<SharedFunctionInfo> shared =
1535         UnwrapSharedFunctionInfoFromJSValue(jsvalue);
1536
1537     if (function->shared() == *shared || IsInlined(*function, *shared)) {
1538       SetElementSloppy(result, i, Handle<Smi>(Smi::FromInt(status), isolate));
1539       return true;
1540     }
1541   }
1542   return false;
1543 }
1544
1545
1546 // Iterates over handler chain and removes all elements that are inside
1547 // frames being dropped.
1548 static bool FixTryCatchHandler(StackFrame* top_frame,
1549                                StackFrame* bottom_frame) {
1550   Address* pointer_address =
1551       &Memory::Address_at(top_frame->isolate()->get_address_from_id(
1552           Isolate::kHandlerAddress));
1553
1554   while (*pointer_address < top_frame->sp()) {
1555     pointer_address = &Memory::Address_at(*pointer_address);
1556   }
1557   Address* above_frame_address = pointer_address;
1558   while (*pointer_address < bottom_frame->fp()) {
1559     pointer_address = &Memory::Address_at(*pointer_address);
1560   }
1561   bool change = *above_frame_address != *pointer_address;
1562   *above_frame_address = *pointer_address;
1563   return change;
1564 }
1565
1566
1567 // Initializes an artificial stack frame. The data it contains is used for:
1568 //  a. successful work of frame dropper code which eventually gets control,
1569 //  b. being compatible with regular stack structure for various stack
1570 //     iterators.
1571 // Returns address of stack allocated pointer to restarted function,
1572 // the value that is called 'restarter_frame_function_pointer'. The value
1573 // at this address (possibly updated by GC) may be used later when preparing
1574 // 'step in' operation.
1575 // Frame structure (conforms InternalFrame structure):
1576 //   -- code
1577 //   -- SMI maker
1578 //   -- function (slot is called "context")
1579 //   -- frame base
1580 static Object** SetUpFrameDropperFrame(StackFrame* bottom_js_frame,
1581                                        Handle<Code> code) {
1582   DCHECK(bottom_js_frame->is_java_script());
1583
1584   Address fp = bottom_js_frame->fp();
1585
1586   // Move function pointer into "context" slot.
1587   Memory::Object_at(fp + StandardFrameConstants::kContextOffset) =
1588       Memory::Object_at(fp + JavaScriptFrameConstants::kFunctionOffset);
1589
1590   Memory::Object_at(fp + InternalFrameConstants::kCodeOffset) = *code;
1591   Memory::Object_at(fp + StandardFrameConstants::kMarkerOffset) =
1592       Smi::FromInt(StackFrame::INTERNAL);
1593
1594   return reinterpret_cast<Object**>(&Memory::Object_at(
1595       fp + StandardFrameConstants::kContextOffset));
1596 }
1597
1598
1599 // Removes specified range of frames from stack. There may be 1 or more
1600 // frames in range. Anyway the bottom frame is restarted rather than dropped,
1601 // and therefore has to be a JavaScript frame.
1602 // Returns error message or NULL.
1603 static const char* DropFrames(Vector<StackFrame*> frames,
1604                               int top_frame_index,
1605                               int bottom_js_frame_index,
1606                               LiveEdit::FrameDropMode* mode,
1607                               Object*** restarter_frame_function_pointer) {
1608   if (!LiveEdit::kFrameDropperSupported) {
1609     return "Stack manipulations are not supported in this architecture.";
1610   }
1611
1612   StackFrame* pre_top_frame = frames[top_frame_index - 1];
1613   StackFrame* top_frame = frames[top_frame_index];
1614   StackFrame* bottom_js_frame = frames[bottom_js_frame_index];
1615
1616   DCHECK(bottom_js_frame->is_java_script());
1617
1618   // Check the nature of the top frame.
1619   Isolate* isolate = bottom_js_frame->isolate();
1620   Code* pre_top_frame_code = pre_top_frame->LookupCode();
1621   bool frame_has_padding = true;
1622   if (pre_top_frame_code->is_inline_cache_stub() &&
1623       pre_top_frame_code->is_debug_stub()) {
1624     // OK, we can drop inline cache calls.
1625     *mode = LiveEdit::FRAME_DROPPED_IN_IC_CALL;
1626   } else if (pre_top_frame_code ==
1627              isolate->builtins()->builtin(Builtins::kSlot_DebugBreak)) {
1628     // OK, we can drop debug break slot.
1629     *mode = LiveEdit::FRAME_DROPPED_IN_DEBUG_SLOT_CALL;
1630   } else if (pre_top_frame_code ==
1631              isolate->builtins()->builtin(Builtins::kFrameDropper_LiveEdit)) {
1632     // OK, we can drop our own code.
1633     pre_top_frame = frames[top_frame_index - 2];
1634     top_frame = frames[top_frame_index - 1];
1635     *mode = LiveEdit::CURRENTLY_SET_MODE;
1636     frame_has_padding = false;
1637   } else if (pre_top_frame_code ==
1638              isolate->builtins()->builtin(Builtins::kReturn_DebugBreak)) {
1639     *mode = LiveEdit::FRAME_DROPPED_IN_RETURN_CALL;
1640   } else if (pre_top_frame_code->kind() == Code::STUB &&
1641              CodeStub::GetMajorKey(pre_top_frame_code) == CodeStub::CEntry) {
1642     // Entry from our unit tests on 'debugger' statement.
1643     // It's fine, we support this case.
1644     *mode = LiveEdit::FRAME_DROPPED_IN_DIRECT_CALL;
1645     // We don't have a padding from 'debugger' statement call.
1646     // Here the stub is CEntry, it's not debug-only and can't be padded.
1647     // If anyone would complain, a proxy padded stub could be added.
1648     frame_has_padding = false;
1649   } else if (pre_top_frame->type() == StackFrame::ARGUMENTS_ADAPTOR) {
1650     // This must be adaptor that remain from the frame dropping that
1651     // is still on stack. A frame dropper frame must be above it.
1652     DCHECK(frames[top_frame_index - 2]->LookupCode() ==
1653            isolate->builtins()->builtin(Builtins::kFrameDropper_LiveEdit));
1654     pre_top_frame = frames[top_frame_index - 3];
1655     top_frame = frames[top_frame_index - 2];
1656     *mode = LiveEdit::CURRENTLY_SET_MODE;
1657     frame_has_padding = false;
1658   } else {
1659     return "Unknown structure of stack above changing function";
1660   }
1661
1662   Address unused_stack_top = top_frame->sp();
1663   int new_frame_size = LiveEdit::kFrameDropperFrameSize * kPointerSize;
1664   Address unused_stack_bottom = bottom_js_frame->fp()
1665       - new_frame_size + kPointerSize;  // Bigger address end is exclusive.
1666
1667   Address* top_frame_pc_address = top_frame->pc_address();
1668
1669   // top_frame may be damaged below this point. Do not used it.
1670   DCHECK(!(top_frame = NULL));
1671
1672   if (unused_stack_top > unused_stack_bottom) {
1673     if (frame_has_padding) {
1674       int shortage_bytes =
1675           static_cast<int>(unused_stack_top - unused_stack_bottom);
1676
1677       Address padding_start = pre_top_frame->fp() -
1678           LiveEdit::kFrameDropperFrameSize * kPointerSize;
1679
1680       Address padding_pointer = padding_start;
1681       Smi* padding_object = Smi::FromInt(LiveEdit::kFramePaddingValue);
1682       while (Memory::Object_at(padding_pointer) == padding_object) {
1683         padding_pointer -= kPointerSize;
1684       }
1685       int padding_counter =
1686           Smi::cast(Memory::Object_at(padding_pointer))->value();
1687       if (padding_counter * kPointerSize < shortage_bytes) {
1688         return "Not enough space for frame dropper frame "
1689             "(even with padding frame)";
1690       }
1691       Memory::Object_at(padding_pointer) =
1692           Smi::FromInt(padding_counter - shortage_bytes / kPointerSize);
1693
1694       StackFrame* pre_pre_frame = frames[top_frame_index - 2];
1695
1696       MemMove(padding_start + kPointerSize - shortage_bytes,
1697               padding_start + kPointerSize,
1698               LiveEdit::kFrameDropperFrameSize * kPointerSize);
1699
1700       pre_top_frame->UpdateFp(pre_top_frame->fp() - shortage_bytes);
1701       pre_pre_frame->SetCallerFp(pre_top_frame->fp());
1702       unused_stack_top -= shortage_bytes;
1703
1704       STATIC_ASSERT(sizeof(Address) == kPointerSize);
1705       top_frame_pc_address -= shortage_bytes / kPointerSize;
1706     } else {
1707       return "Not enough space for frame dropper frame";
1708     }
1709   }
1710
1711   // Committing now. After this point we should return only NULL value.
1712
1713   FixTryCatchHandler(pre_top_frame, bottom_js_frame);
1714   // Make sure FixTryCatchHandler is idempotent.
1715   DCHECK(!FixTryCatchHandler(pre_top_frame, bottom_js_frame));
1716
1717   Handle<Code> code = isolate->builtins()->FrameDropper_LiveEdit();
1718   *top_frame_pc_address = code->entry();
1719   pre_top_frame->SetCallerFp(bottom_js_frame->fp());
1720
1721   *restarter_frame_function_pointer =
1722       SetUpFrameDropperFrame(bottom_js_frame, code);
1723
1724   DCHECK((**restarter_frame_function_pointer)->IsJSFunction());
1725
1726   for (Address a = unused_stack_top;
1727       a < unused_stack_bottom;
1728       a += kPointerSize) {
1729     Memory::Object_at(a) = Smi::FromInt(0);
1730   }
1731
1732   return NULL;
1733 }
1734
1735
1736 // Describes a set of call frames that execute any of listed functions.
1737 // Finding no such frames does not mean error.
1738 class MultipleFunctionTarget {
1739  public:
1740   MultipleFunctionTarget(Handle<JSArray> shared_info_array,
1741       Handle<JSArray> result)
1742       : m_shared_info_array(shared_info_array),
1743         m_result(result) {}
1744   bool MatchActivation(StackFrame* frame,
1745       LiveEdit::FunctionPatchabilityStatus status) {
1746     return CheckActivation(m_shared_info_array, m_result, frame, status);
1747   }
1748   const char* GetNotFoundMessage() const {
1749     return NULL;
1750   }
1751  private:
1752   Handle<JSArray> m_shared_info_array;
1753   Handle<JSArray> m_result;
1754 };
1755
1756
1757 // Drops all call frame matched by target and all frames above them.
1758 template<typename TARGET>
1759 static const char* DropActivationsInActiveThreadImpl(
1760     Isolate* isolate,
1761     TARGET& target,  // NOLINT
1762     bool do_drop) {
1763   Debug* debug = isolate->debug();
1764   Zone zone(isolate);
1765   Vector<StackFrame*> frames = CreateStackMap(isolate, &zone);
1766
1767
1768   int top_frame_index = -1;
1769   int frame_index = 0;
1770   for (; frame_index < frames.length(); frame_index++) {
1771     StackFrame* frame = frames[frame_index];
1772     if (frame->id() == debug->break_frame_id()) {
1773       top_frame_index = frame_index;
1774       break;
1775     }
1776     if (target.MatchActivation(
1777             frame, LiveEdit::FUNCTION_BLOCKED_UNDER_NATIVE_CODE)) {
1778       // We are still above break_frame. It is not a target frame,
1779       // it is a problem.
1780       return "Debugger mark-up on stack is not found";
1781     }
1782   }
1783
1784   if (top_frame_index == -1) {
1785     // We haven't found break frame, but no function is blocking us anyway.
1786     return target.GetNotFoundMessage();
1787   }
1788
1789   bool target_frame_found = false;
1790   int bottom_js_frame_index = top_frame_index;
1791   bool non_droppable_frame_found = false;
1792   LiveEdit::FunctionPatchabilityStatus non_droppable_reason;
1793
1794   for (; frame_index < frames.length(); frame_index++) {
1795     StackFrame* frame = frames[frame_index];
1796     if (frame->is_exit()) {
1797       non_droppable_frame_found = true;
1798       non_droppable_reason = LiveEdit::FUNCTION_BLOCKED_UNDER_NATIVE_CODE;
1799       break;
1800     }
1801     if (frame->is_java_script() &&
1802         JavaScriptFrame::cast(frame)->function()->shared()->is_generator()) {
1803       non_droppable_frame_found = true;
1804       non_droppable_reason = LiveEdit::FUNCTION_BLOCKED_UNDER_GENERATOR;
1805       break;
1806     }
1807     if (target.MatchActivation(
1808             frame, LiveEdit::FUNCTION_BLOCKED_ON_ACTIVE_STACK)) {
1809       target_frame_found = true;
1810       bottom_js_frame_index = frame_index;
1811     }
1812   }
1813
1814   if (non_droppable_frame_found) {
1815     // There is a C or generator frame on stack.  We can't drop C frames, and we
1816     // can't restart generators.  Check that there are no target frames below
1817     // them.
1818     for (; frame_index < frames.length(); frame_index++) {
1819       StackFrame* frame = frames[frame_index];
1820       if (frame->is_java_script()) {
1821         if (target.MatchActivation(frame, non_droppable_reason)) {
1822           // Fail.
1823           return NULL;
1824         }
1825       }
1826     }
1827   }
1828
1829   if (!do_drop) {
1830     // We are in check-only mode.
1831     return NULL;
1832   }
1833
1834   if (!target_frame_found) {
1835     // Nothing to drop.
1836     return target.GetNotFoundMessage();
1837   }
1838
1839   LiveEdit::FrameDropMode drop_mode = LiveEdit::FRAMES_UNTOUCHED;
1840   Object** restarter_frame_function_pointer = NULL;
1841   const char* error_message = DropFrames(frames, top_frame_index,
1842                                          bottom_js_frame_index, &drop_mode,
1843                                          &restarter_frame_function_pointer);
1844
1845   if (error_message != NULL) {
1846     return error_message;
1847   }
1848
1849   // Adjust break_frame after some frames has been dropped.
1850   StackFrame::Id new_id = StackFrame::NO_ID;
1851   for (int i = bottom_js_frame_index + 1; i < frames.length(); i++) {
1852     if (frames[i]->type() == StackFrame::JAVA_SCRIPT) {
1853       new_id = frames[i]->id();
1854       break;
1855     }
1856   }
1857   debug->FramesHaveBeenDropped(
1858       new_id, drop_mode, restarter_frame_function_pointer);
1859   return NULL;
1860 }
1861
1862
1863 // Fills result array with statuses of functions. Modifies the stack
1864 // removing all listed function if possible and if do_drop is true.
1865 static const char* DropActivationsInActiveThread(
1866     Handle<JSArray> shared_info_array, Handle<JSArray> result, bool do_drop) {
1867   MultipleFunctionTarget target(shared_info_array, result);
1868
1869   const char* message = DropActivationsInActiveThreadImpl(
1870       shared_info_array->GetIsolate(), target, do_drop);
1871   if (message) {
1872     return message;
1873   }
1874
1875   Isolate* isolate = shared_info_array->GetIsolate();
1876   int array_len = GetArrayLength(shared_info_array);
1877
1878   // Replace "blocked on active" with "replaced on active" status.
1879   for (int i = 0; i < array_len; i++) {
1880     Handle<Object> obj =
1881         Object::GetElement(isolate, result, i).ToHandleChecked();
1882     if (*obj == Smi::FromInt(LiveEdit::FUNCTION_BLOCKED_ON_ACTIVE_STACK)) {
1883       Handle<Object> replaced(
1884           Smi::FromInt(LiveEdit::FUNCTION_REPLACED_ON_ACTIVE_STACK), isolate);
1885       SetElementSloppy(result, i, replaced);
1886     }
1887   }
1888   return NULL;
1889 }
1890
1891
1892 bool LiveEdit::FindActiveGenerators(Handle<FixedArray> shared_info_array,
1893                                     Handle<FixedArray> result,
1894                                     int len) {
1895   Isolate* isolate = shared_info_array->GetIsolate();
1896   bool found_suspended_activations = false;
1897
1898   DCHECK_LE(len, result->length());
1899
1900   FunctionPatchabilityStatus active = FUNCTION_BLOCKED_ACTIVE_GENERATOR;
1901
1902   Heap* heap = isolate->heap();
1903   HeapIterator iterator(heap);
1904   HeapObject* obj = NULL;
1905   while ((obj = iterator.next()) != NULL) {
1906     if (!obj->IsJSGeneratorObject()) continue;
1907
1908     JSGeneratorObject* gen = JSGeneratorObject::cast(obj);
1909     if (gen->is_closed()) continue;
1910
1911     HandleScope scope(isolate);
1912
1913     for (int i = 0; i < len; i++) {
1914       Handle<JSValue> jsvalue =
1915           Handle<JSValue>::cast(FixedArray::get(shared_info_array, i));
1916       Handle<SharedFunctionInfo> shared =
1917           UnwrapSharedFunctionInfoFromJSValue(jsvalue);
1918
1919       if (gen->function()->shared() == *shared) {
1920         result->set(i, Smi::FromInt(active));
1921         found_suspended_activations = true;
1922       }
1923     }
1924   }
1925
1926   return found_suspended_activations;
1927 }
1928
1929
1930 class InactiveThreadActivationsChecker : public ThreadVisitor {
1931  public:
1932   InactiveThreadActivationsChecker(Handle<JSArray> shared_info_array,
1933                                    Handle<JSArray> result)
1934       : shared_info_array_(shared_info_array), result_(result),
1935         has_blocked_functions_(false) {
1936   }
1937   void VisitThread(Isolate* isolate, ThreadLocalTop* top) {
1938     for (StackFrameIterator it(isolate, top); !it.done(); it.Advance()) {
1939       has_blocked_functions_ |= CheckActivation(
1940           shared_info_array_, result_, it.frame(),
1941           LiveEdit::FUNCTION_BLOCKED_ON_OTHER_STACK);
1942     }
1943   }
1944   bool HasBlockedFunctions() {
1945     return has_blocked_functions_;
1946   }
1947
1948  private:
1949   Handle<JSArray> shared_info_array_;
1950   Handle<JSArray> result_;
1951   bool has_blocked_functions_;
1952 };
1953
1954
1955 Handle<JSArray> LiveEdit::CheckAndDropActivations(
1956     Handle<JSArray> shared_info_array, bool do_drop) {
1957   Isolate* isolate = shared_info_array->GetIsolate();
1958   int len = GetArrayLength(shared_info_array);
1959
1960   DCHECK(shared_info_array->HasFastElements());
1961   Handle<FixedArray> shared_info_array_elements(
1962       FixedArray::cast(shared_info_array->elements()));
1963
1964   Handle<JSArray> result = isolate->factory()->NewJSArray(len);
1965   Handle<FixedArray> result_elements =
1966       JSObject::EnsureWritableFastElements(result);
1967
1968   // Fill the default values.
1969   for (int i = 0; i < len; i++) {
1970     FunctionPatchabilityStatus status = FUNCTION_AVAILABLE_FOR_PATCH;
1971     result_elements->set(i, Smi::FromInt(status));
1972   }
1973
1974   // Scan the heap for active generators -- those that are either currently
1975   // running (as we wouldn't want to restart them, because we don't know where
1976   // to restart them from) or suspended.  Fail if any one corresponds to the set
1977   // of functions being edited.
1978   if (FindActiveGenerators(shared_info_array_elements, result_elements, len)) {
1979     return result;
1980   }
1981
1982   // Check inactive threads. Fail if some functions are blocked there.
1983   InactiveThreadActivationsChecker inactive_threads_checker(shared_info_array,
1984                                                             result);
1985   isolate->thread_manager()->IterateArchivedThreads(
1986       &inactive_threads_checker);
1987   if (inactive_threads_checker.HasBlockedFunctions()) {
1988     return result;
1989   }
1990
1991   // Try to drop activations from the current stack.
1992   const char* error_message =
1993       DropActivationsInActiveThread(shared_info_array, result, do_drop);
1994   if (error_message != NULL) {
1995     // Add error message as an array extra element.
1996     Handle<String> str =
1997         isolate->factory()->NewStringFromAsciiChecked(error_message);
1998     SetElementSloppy(result, len, str);
1999   }
2000   return result;
2001 }
2002
2003
2004 // Describes a single callframe a target. Not finding this frame
2005 // means an error.
2006 class SingleFrameTarget {
2007  public:
2008   explicit SingleFrameTarget(JavaScriptFrame* frame)
2009       : m_frame(frame),
2010         m_saved_status(LiveEdit::FUNCTION_AVAILABLE_FOR_PATCH) {}
2011
2012   bool MatchActivation(StackFrame* frame,
2013       LiveEdit::FunctionPatchabilityStatus status) {
2014     if (frame->fp() == m_frame->fp()) {
2015       m_saved_status = status;
2016       return true;
2017     }
2018     return false;
2019   }
2020   const char* GetNotFoundMessage() const {
2021     return "Failed to found requested frame";
2022   }
2023   LiveEdit::FunctionPatchabilityStatus saved_status() {
2024     return m_saved_status;
2025   }
2026  private:
2027   JavaScriptFrame* m_frame;
2028   LiveEdit::FunctionPatchabilityStatus m_saved_status;
2029 };
2030
2031
2032 // Finds a drops required frame and all frames above.
2033 // Returns error message or NULL.
2034 const char* LiveEdit::RestartFrame(JavaScriptFrame* frame) {
2035   SingleFrameTarget target(frame);
2036
2037   const char* result = DropActivationsInActiveThreadImpl(
2038       frame->isolate(), target, true);
2039   if (result != NULL) {
2040     return result;
2041   }
2042   if (target.saved_status() == LiveEdit::FUNCTION_BLOCKED_UNDER_NATIVE_CODE) {
2043     return "Function is blocked under native code";
2044   }
2045   if (target.saved_status() == LiveEdit::FUNCTION_BLOCKED_UNDER_GENERATOR) {
2046     return "Function is blocked under a generator activation";
2047   }
2048   return NULL;
2049 }
2050
2051
2052 LiveEditFunctionTracker::LiveEditFunctionTracker(Isolate* isolate,
2053                                                  FunctionLiteral* fun)
2054     : isolate_(isolate) {
2055   if (isolate_->active_function_info_listener() != NULL) {
2056     isolate_->active_function_info_listener()->FunctionStarted(fun);
2057   }
2058 }
2059
2060
2061 LiveEditFunctionTracker::~LiveEditFunctionTracker() {
2062   if (isolate_->active_function_info_listener() != NULL) {
2063     isolate_->active_function_info_listener()->FunctionDone();
2064   }
2065 }
2066
2067
2068 void LiveEditFunctionTracker::RecordFunctionInfo(
2069     Handle<SharedFunctionInfo> info, FunctionLiteral* lit,
2070     Zone* zone) {
2071   if (isolate_->active_function_info_listener() != NULL) {
2072     isolate_->active_function_info_listener()->FunctionInfo(info, lit->scope(),
2073                                                             zone);
2074   }
2075 }
2076
2077
2078 void LiveEditFunctionTracker::RecordRootFunctionInfo(Handle<Code> code) {
2079   isolate_->active_function_info_listener()->FunctionCode(code);
2080 }
2081
2082
2083 bool LiveEditFunctionTracker::IsActive(Isolate* isolate) {
2084   return isolate->active_function_info_listener() != NULL;
2085 }
2086
2087 } }  // namespace v8::internal