Home | History | Annotate | Download | only in src
      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
   2088