liveedit.cc 46.5 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/debug/liveedit.h"
6

7
#include "src/api-inl.h"
8 9
#include "src/ast/ast-traversal-visitor.h"
#include "src/ast/ast.h"
10
#include "src/ast/scopes.h"
11 12
#include "src/compilation-cache.h"
#include "src/compiler.h"
13
#include "src/debug/debug-interface.h"
14
#include "src/debug/debug.h"
15
#include "src/frames-inl.h"
16
#include "src/isolate-inl.h"
17
#include "src/objects-inl.h"
18
#include "src/objects/hash-table-inl.h"
19
#include "src/objects/js-generator-inl.h"
20 21
#include "src/parsing/parse-info.h"
#include "src/parsing/parsing.h"
22
#include "src/source-position-table.h"
23
#include "src/v8.h"
24 25 26

namespace v8 {
namespace internal {
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
namespace {
// A general-purpose comparator between 2 arrays.
class Comparator {
 public:
  // Holds 2 arrays of some elements allowing to compare any pair of
  // element from the first array and element from the second array.
  class Input {
   public:
    virtual int GetLength1() = 0;
    virtual int GetLength2() = 0;
    virtual bool Equals(int index1, int index2) = 0;

   protected:
    virtual ~Input() = default;
  };

  // Receives compare result as a series of chunks.
  class Output {
   public:
    // Puts another chunk in result list. Note that technically speaking
    // only 3 arguments actually needed with 4th being derivable.
    virtual void AddChunk(int pos1, int pos2, int len1, int len2) = 0;

   protected:
    virtual ~Output() = default;
  };

  // Finds the difference between 2 arrays of elements.
  static void CalculateDifference(Input* input, Output* result_writer);
};
57

58
// A simple implementation of dynamic programming algorithm. It solves
59 60
// the problem of finding the difference of 2 arrays. It uses a table of results
// of subproblems. Each cell contains a number together with 2-bit flag
61 62 63
// that helps building the chunk list.
class Differencer {
 public:
64 65 66
  explicit Differencer(Comparator::Input* input)
      : input_(input), len1_(input->GetLength1()), len2_(input->GetLength2()) {
    buffer_ = NewArray<int>(len1_ * len2_);
67 68
  }
  ~Differencer() {
69
    DeleteArray(buffer_);
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
  }

  void Initialize() {
    int array_size = len1_ * len2_;
    for (int i = 0; i < array_size; i++) {
      buffer_[i] = kEmptyCellValue;
    }
  }

  // Makes sure that result for the full problem is calculated and stored
  // in the table together with flags showing a path through subproblems.
  void FillTable() {
    CompareUpToTail(0, 0);
  }

85
  void SaveResult(Comparator::Output* chunk_writer) {
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
    ResultWriter writer(chunk_writer);

    int pos1 = 0;
    int pos2 = 0;
    while (true) {
      if (pos1 < len1_) {
        if (pos2 < len2_) {
          Direction dir = get_direction(pos1, pos2);
          switch (dir) {
            case EQ:
              writer.eq();
              pos1++;
              pos2++;
              break;
            case SKIP1:
              writer.skip1(1);
              pos1++;
              break;
            case SKIP2:
            case SKIP_ANY:
              writer.skip2(1);
              pos2++;
              break;
            default:
              UNREACHABLE();
          }
        } else {
          writer.skip1(len1_ - pos1);
          break;
        }
      } else {
        if (len2_ != pos2) {
          writer.skip2(len2_ - pos2);
        }
        break;
      }
    }
    writer.close();
  }

 private:
127
  Comparator::Input* input_;
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
  int* buffer_;
  int len1_;
  int len2_;

  enum Direction {
    EQ = 0,
    SKIP1,
    SKIP2,
    SKIP_ANY,

    MAX_DIRECTION_FLAG_VALUE = SKIP_ANY
  };

  // Computes result for a subtask and optionally caches it in the buffer table.
  // All results values are shifted to make space for flags in the lower bits.
  int CompareUpToTail(int pos1, int pos2) {
    if (pos1 < len1_) {
      if (pos2 < len2_) {
        int cached_res = get_value4(pos1, pos2);
        if (cached_res == kEmptyCellValue) {
          Direction dir;
          int res;
150
          if (input_->Equals(pos1, pos2)) {
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
            res = CompareUpToTail(pos1 + 1, pos2 + 1);
            dir = EQ;
          } else {
            int res1 = CompareUpToTail(pos1 + 1, pos2) +
                (1 << kDirectionSizeBits);
            int res2 = CompareUpToTail(pos1, pos2 + 1) +
                (1 << kDirectionSizeBits);
            if (res1 == res2) {
              res = res1;
              dir = SKIP_ANY;
            } else if (res1 < res2) {
              res = res1;
              dir = SKIP1;
            } else {
              res = res2;
              dir = SKIP2;
            }
          }
          set_value4_and_dir(pos1, pos2, res, dir);
          cached_res = res;
        }
        return cached_res;
      } else {
        return (len1_ - pos1) << kDirectionSizeBits;
      }
    } else {
      return (len2_ - pos2) << kDirectionSizeBits;
    }
  }

  inline int& get_cell(int i1, int i2) {
    return buffer_[i1 + i2 * len1_];
  }

  // Each cell keeps a value plus direction. Value is multiplied by 4.
  void set_value4_and_dir(int i1, int i2, int value4, Direction dir) {
187
    DCHECK_EQ(0, value4 & kDirectionMask);
188 189 190 191 192 193 194 195 196 197 198 199
    get_cell(i1, i2) = value4 | dir;
  }

  int get_value4(int i1, int i2) {
    return get_cell(i1, i2) & (kMaxUInt32 ^ kDirectionMask);
  }
  Direction get_direction(int i1, int i2) {
    return static_cast<Direction>(get_cell(i1, i2) & kDirectionMask);
  }

  static const int kDirectionSizeBits = 2;
  static const int kDirectionMask = (1 << kDirectionSizeBits) - 1;
200
  static const int kEmptyCellValue = ~0u << kDirectionSizeBits;
201 202 203 204 205 206 207 208 209

  // This method only holds static assert statement (unfortunately you cannot
  // place one in class scope).
  void StaticAssertHolder() {
    STATIC_ASSERT(MAX_DIRECTION_FLAG_VALUE < (1 << kDirectionSizeBits));
  }

  class ResultWriter {
   public:
210
    explicit ResultWriter(Comparator::Output* chunk_writer)
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
        : chunk_writer_(chunk_writer), pos1_(0), pos2_(0),
          pos1_begin_(-1), pos2_begin_(-1), has_open_chunk_(false) {
    }
    void eq() {
      FlushChunk();
      pos1_++;
      pos2_++;
    }
    void skip1(int len1) {
      StartChunk();
      pos1_ += len1;
    }
    void skip2(int len2) {
      StartChunk();
      pos2_ += len2;
    }
    void close() {
      FlushChunk();
    }

   private:
232
    Comparator::Output* chunk_writer_;
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
    int pos1_;
    int pos2_;
    int pos1_begin_;
    int pos2_begin_;
    bool has_open_chunk_;

    void StartChunk() {
      if (!has_open_chunk_) {
        pos1_begin_ = pos1_;
        pos2_begin_ = pos2_;
        has_open_chunk_ = true;
      }
    }

    void FlushChunk() {
      if (has_open_chunk_) {
        chunk_writer_->AddChunk(pos1_begin_, pos2_begin_,
                                pos1_ - pos1_begin_, pos2_ - pos2_begin_);
        has_open_chunk_ = false;
      }
    }
  };
};

257 258 259
void Comparator::CalculateDifference(Comparator::Input* input,
                                     Comparator::Output* result_writer) {
  Differencer differencer(input);
260 261 262 263 264
  differencer.Initialize();
  differencer.FillTable();
  differencer.SaveResult(result_writer);
}

265 266
bool CompareSubstrings(Handle<String> s1, int pos1, Handle<String> s2, int pos2,
                       int len) {
267
  for (int i = 0; i < len; i++) {
268
    if (s1->Get(i + pos1) != s2->Get(i + pos2)) return false;
269 270 271 272
  }
  return true;
}

273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
// Additional to Input interface. Lets switch Input range to subrange.
// More elegant way would be to wrap one Input as another Input object
// and translate positions there, but that would cost us additional virtual
// call per comparison.
class SubrangableInput : public Comparator::Input {
 public:
  virtual void SetSubrange1(int offset, int len) = 0;
  virtual void SetSubrange2(int offset, int len) = 0;
};


class SubrangableOutput : public Comparator::Output {
 public:
  virtual void SetSubrange1(int offset, int len) = 0;
  virtual void SetSubrange2(int offset, int len) = 0;
};

// Finds common prefix and suffix in input. This parts shouldn't take space in
// linear programming table. Enable subranging in input and output.
292
void NarrowDownInput(SubrangableInput* input, SubrangableOutput* output) {
293 294 295 296 297 298 299 300
  const int len1 = input->GetLength1();
  const int len2 = input->GetLength2();

  int common_prefix_len;
  int common_suffix_len;

  {
    common_prefix_len = 0;
301
    int prefix_limit = std::min(len1, len2);
302 303 304 305 306 307
    while (common_prefix_len < prefix_limit &&
        input->Equals(common_prefix_len, common_prefix_len)) {
      common_prefix_len++;
    }

    common_suffix_len = 0;
308 309
    int suffix_limit =
        std::min(len1 - common_prefix_len, len2 - common_prefix_len);
310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329

    while (common_suffix_len < suffix_limit &&
        input->Equals(len1 - common_suffix_len - 1,
        len2 - common_suffix_len - 1)) {
      common_suffix_len++;
    }
  }

  if (common_prefix_len > 0 || common_suffix_len > 0) {
    int new_len1 = len1 - common_suffix_len - common_prefix_len;
    int new_len2 = len2 - common_suffix_len - common_prefix_len;

    input->SetSubrange1(common_prefix_len, new_len1);
    input->SetSubrange2(common_prefix_len, new_len2);

    output->SetSubrange1(common_prefix_len, new_len1);
    output->SetSubrange2(common_prefix_len, new_len2);
  }
}

330 331 332 333 334 335 336 337 338 339
// Represents 2 strings as 2 arrays of tokens.
// TODO(LiveEdit): Currently it's actually an array of charactres.
//     Make array of tokens instead.
class TokensCompareInput : public Comparator::Input {
 public:
  TokensCompareInput(Handle<String> s1, int offset1, int len1,
                       Handle<String> s2, int offset2, int len2)
      : s1_(s1), offset1_(offset1), len1_(len1),
        s2_(s2), offset2_(offset2), len2_(len2) {
  }
340 341 342
  int GetLength1() override { return len1_; }
  int GetLength2() override { return len2_; }
  bool Equals(int index1, int index2) override {
343 344 345 346 347 348 349 350 351 352 353 354
    return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
  }

 private:
  Handle<String> s1_;
  int offset1_;
  int len1_;
  Handle<String> s2_;
  int offset2_;
  int len2_;
};

355
// Stores compare result in std::vector. Converts substring positions
356 357 358
// to absolute positions.
class TokensCompareOutput : public Comparator::Output {
 public:
359 360 361
  TokensCompareOutput(int offset1, int offset2,
                      std::vector<SourceChangeRange>* output)
      : output_(output), offset1_(offset1), offset2_(offset2) {}
362

363 364 365 366
  void AddChunk(int pos1, int pos2, int len1, int len2) override {
    output_->emplace_back(
        SourceChangeRange{pos1 + offset1_, pos1 + len1 + offset1_,
                          pos2 + offset2_, pos2 + offset2_ + len2});
367 368 369
  }

 private:
370
  std::vector<SourceChangeRange>* output_;
371 372 373 374
  int offset1_;
  int offset2_;
};

375 376 377 378
// Wraps raw n-elements line_ends array as a list of n+1 lines. The last line
// never has terminating new line character.
class LineEndsWrapper {
 public:
379 380 381
  explicit LineEndsWrapper(Isolate* isolate, Handle<String> string)
      : ends_array_(String::CalculateLineEnds(isolate, string, false)),
        string_len_(string->length()) {}
382 383 384 385 386
  int length() {
    return ends_array_->length() + 1;
  }
  // Returns start for any line including start of the imaginary line after
  // the last line.
387
  int GetLineStart(int index) { return index == 0 ? 0 : GetLineEnd(index - 1); }
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403
  int GetLineEnd(int index) {
    if (index == ends_array_->length()) {
      // End of the last line is always an end of the whole string.
      // If the string ends with a new line character, the last line is an
      // empty string after this character.
      return string_len_;
    } else {
      return GetPosAfterNewLine(index);
    }
  }

 private:
  Handle<FixedArray> ends_array_;
  int string_len_;

  int GetPosAfterNewLine(int index) {
jgruber's avatar
jgruber committed
404
    return Smi::ToInt(ends_array_->get(index)) + 1;
405 406 407 408
  }
};

// Represents 2 strings as 2 arrays of lines.
409
class LineArrayCompareInput : public SubrangableInput {
410
 public:
411
  LineArrayCompareInput(Handle<String> s1, Handle<String> s2,
412
                        LineEndsWrapper line_ends1, LineEndsWrapper line_ends2)
413
      : s1_(s1), s2_(s2), line_ends1_(line_ends1),
414 415 416 417
        line_ends2_(line_ends2),
        subrange_offset1_(0), subrange_offset2_(0),
        subrange_len1_(line_ends1_.length()),
        subrange_len2_(line_ends2_.length()) {
418
  }
419 420 421
  int GetLength1() override { return subrange_len1_; }
  int GetLength2() override { return subrange_len2_; }
  bool Equals(int index1, int index2) override {
422 423 424
    index1 += subrange_offset1_;
    index2 += subrange_offset2_;

425 426 427 428 429 430 431 432 433
    int line_start1 = line_ends1_.GetLineStart(index1);
    int line_start2 = line_ends2_.GetLineStart(index2);
    int line_end1 = line_ends1_.GetLineEnd(index1);
    int line_end2 = line_ends2_.GetLineEnd(index2);
    int len1 = line_end1 - line_start1;
    int len2 = line_end2 - line_start2;
    if (len1 != len2) {
      return false;
    }
434
    return CompareSubstrings(s1_, line_start1, s2_, line_start2,
435
                             len1);
436
  }
437
  void SetSubrange1(int offset, int len) override {
438 439 440
    subrange_offset1_ = offset;
    subrange_len1_ = len;
  }
441
  void SetSubrange2(int offset, int len) override {
442 443 444
    subrange_offset2_ = offset;
    subrange_len2_ = len;
  }
445 446 447 448 449 450

 private:
  Handle<String> s1_;
  Handle<String> s2_;
  LineEndsWrapper line_ends1_;
  LineEndsWrapper line_ends2_;
451 452 453 454
  int subrange_offset1_;
  int subrange_offset2_;
  int subrange_len1_;
  int subrange_len2_;
455 456
};

457
// Stores compare result in std::vector. For each chunk tries to conduct
458
// a fine-grained nested diff token-wise.
459
class TokenizingLineArrayCompareOutput : public SubrangableOutput {
460
 public:
461
  TokenizingLineArrayCompareOutput(Isolate* isolate, LineEndsWrapper line_ends1,
462
                                   LineEndsWrapper line_ends2,
463 464
                                   Handle<String> s1, Handle<String> s2,
                                   std::vector<SourceChangeRange>* output)
465 466 467 468 469 470
      : isolate_(isolate),
        line_ends1_(line_ends1),
        line_ends2_(line_ends2),
        s1_(s1),
        s2_(s2),
        subrange_offset1_(0),
471 472
        subrange_offset2_(0),
        output_(output) {}
473

474 475
  void AddChunk(int line_pos1, int line_pos2, int line_len1,
                int line_len2) override {
476 477 478
    line_pos1 += subrange_offset1_;
    line_pos2 += subrange_offset2_;

479 480 481 482 483
    int char_pos1 = line_ends1_.GetLineStart(line_pos1);
    int char_pos2 = line_ends2_.GetLineStart(line_pos2);
    int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1;
    int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) - char_pos2;

484 485
    if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
      // Chunk is small enough to conduct a nested token-level diff.
486
      HandleScope subTaskScope(isolate_);
487 488 489

      TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
                                      s2_, char_pos2, char_len2);
490
      TokensCompareOutput tokens_output(char_pos1, char_pos2, output_);
491

492
      Comparator::CalculateDifference(&tokens_input, &tokens_output);
493
    } else {
494 495
      output_->emplace_back(SourceChangeRange{
          char_pos1, char_pos1 + char_len1, char_pos2, char_pos2 + char_len2});
496
    }
497
  }
498
  void SetSubrange1(int offset, int len) override {
499 500
    subrange_offset1_ = offset;
  }
501
  void SetSubrange2(int offset, int len) override {
502 503
    subrange_offset2_ = offset;
  }
504 505

 private:
506 507
  static const int CHUNK_LEN_LIMIT = 800;

508
  Isolate* isolate_;
509 510
  LineEndsWrapper line_ends1_;
  LineEndsWrapper line_ends2_;
511 512
  Handle<String> s1_;
  Handle<String> s2_;
513 514
  int subrange_offset1_;
  int subrange_offset2_;
515
  std::vector<SourceChangeRange>* output_;
516
};
517

518 519
struct SourcePositionEvent {
  enum Type { LITERAL_STARTS, LITERAL_ENDS, DIFF_STARTS, DIFF_ENDS };
520

521 522
  int position;
  Type type;
523

524 525 526 527
  union {
    FunctionLiteral* literal;
    int pos_diff;
  };
528

529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
  SourcePositionEvent(FunctionLiteral* literal, bool is_start)
      : position(is_start ? literal->start_position()
                          : literal->end_position()),
        type(is_start ? LITERAL_STARTS : LITERAL_ENDS),
        literal(literal) {}
  SourcePositionEvent(const SourceChangeRange& change, bool is_start)
      : position(is_start ? change.start_position : change.end_position),
        type(is_start ? DIFF_STARTS : DIFF_ENDS),
        pos_diff((change.new_end_position - change.new_start_position) -
                 (change.end_position - change.start_position)) {}

  static bool LessThan(const SourcePositionEvent& a,
                       const SourcePositionEvent& b) {
    if (a.position != b.position) return a.position < b.position;
    if (a.type != b.type) return a.type < b.type;
    if (a.type == LITERAL_STARTS && b.type == LITERAL_STARTS) {
545 546 547 548 549 550 551 552 553
      // If the literals start in the same position, we want the one with the
      // furthest (i.e. largest) end position to be first.
      if (a.literal->end_position() != b.literal->end_position()) {
        return a.literal->end_position() > b.literal->end_position();
      }
      // If they also end in the same position, we want the first in order of
      // literal ids to be first.
      return a.literal->function_literal_id() <
             b.literal->function_literal_id();
554
    } else if (a.type == LITERAL_ENDS && b.type == LITERAL_ENDS) {
555 556 557 558 559 560 561 562 563
      // If the literals end in the same position, we want the one with the
      // nearest (i.e. largest) start position to be first.
      if (a.literal->start_position() != b.literal->start_position()) {
        return a.literal->start_position() > b.literal->start_position();
      }
      // If they also end in the same position, we want the last in order of
      // literal ids to be first.
      return a.literal->function_literal_id() >
             b.literal->function_literal_id();
564 565
    } else {
      return a.pos_diff < b.pos_diff;
566 567
    }
  }
568
};
569

570 571 572 573 574 575 576 577 578 579 580 581 582 583
struct FunctionLiteralChange {
  // If any of start/end position is kNoSourcePosition, this literal is
  // considered damaged and will not be mapped and edited at all.
  int new_start_position;
  int new_end_position;
  bool has_changes;
  FunctionLiteral* outer_literal;

  explicit FunctionLiteralChange(int new_start_position, FunctionLiteral* outer)
      : new_start_position(new_start_position),
        new_end_position(kNoSourcePosition),
        has_changes(false),
        outer_literal(outer) {}
};
584

585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
using FunctionLiteralChanges =
    std::unordered_map<FunctionLiteral*, FunctionLiteralChange>;
void CalculateFunctionLiteralChanges(
    const std::vector<FunctionLiteral*>& literals,
    const std::vector<SourceChangeRange>& diffs,
    FunctionLiteralChanges* result) {
  std::vector<SourcePositionEvent> events;
  events.reserve(literals.size() * 2 + diffs.size() * 2);
  for (FunctionLiteral* literal : literals) {
    events.emplace_back(literal, true);
    events.emplace_back(literal, false);
  }
  for (const SourceChangeRange& diff : diffs) {
    events.emplace_back(diff, true);
    events.emplace_back(diff, false);
  }
  std::sort(events.begin(), events.end(), SourcePositionEvent::LessThan);
  bool inside_diff = false;
  int delta = 0;
  std::stack<std::pair<FunctionLiteral*, FunctionLiteralChange>> literal_stack;
  for (const SourcePositionEvent& event : events) {
    switch (event.type) {
      case SourcePositionEvent::DIFF_ENDS:
        DCHECK(inside_diff);
        inside_diff = false;
        delta += event.pos_diff;
        break;
      case SourcePositionEvent::LITERAL_ENDS: {
        DCHECK_EQ(literal_stack.top().first, event.literal);
        FunctionLiteralChange& change = literal_stack.top().second;
        change.new_end_position = inside_diff
                                      ? kNoSourcePosition
                                      : event.literal->end_position() + delta;
        result->insert(literal_stack.top());
        literal_stack.pop();
        break;
      }
      case SourcePositionEvent::LITERAL_STARTS:
        literal_stack.push(std::make_pair(
            event.literal,
            FunctionLiteralChange(
                inside_diff ? kNoSourcePosition
                            : event.literal->start_position() + delta,
                literal_stack.empty() ? nullptr : literal_stack.top().first)));
        break;
      case SourcePositionEvent::DIFF_STARTS:
        DCHECK(!inside_diff);
        inside_diff = true;
        if (!literal_stack.empty()) {
          // Note that outer literal has not necessarily changed, unless the
          // diff goes past the end of this literal. In this case, we'll mark
          // this function as damaged and parent as changed later in
          // MapLiterals.
          literal_stack.top().second.has_changes = true;
        }
        break;
    }
642
  }
643
}
644

645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
// Function which has not changed itself, but if any variable in its
// outer context has been added/removed, we must consider this function
// as damaged and not update references to it.
// This is because old compiled function has hardcoded references to
// it's outer context.
bool HasChangedScope(FunctionLiteral* a, FunctionLiteral* b) {
  Scope* scope_a = a->scope()->outer_scope();
  Scope* scope_b = b->scope()->outer_scope();
  while (scope_a && scope_b) {
    std::unordered_map<int, Handle<String>> vars;
    for (Variable* var : *scope_a->locals()) {
      if (!var->IsContextSlot()) continue;
      vars[var->index()] = var->name();
    }
    for (Variable* var : *scope_b->locals()) {
      if (!var->IsContextSlot()) continue;
      auto it = vars.find(var->index());
      if (it == vars.end()) return true;
      if (*it->second != *var->name()) return true;
664
    }
665 666
    scope_a = scope_a->outer_scope();
    scope_b = scope_b->outer_scope();
667
  }
668 669
  return scope_a != scope_b;
}
670

671 672 673 674 675 676
enum ChangeState { UNCHANGED, CHANGED, DAMAGED };

using LiteralMap = std::unordered_map<FunctionLiteral*, FunctionLiteral*>;
void MapLiterals(const FunctionLiteralChanges& changes,
                 const std::vector<FunctionLiteral*>& new_literals,
                 LiteralMap* unchanged, LiteralMap* changed) {
677 678 679
  // Track the top-level script function separately as it can overlap fully with
  // another function, e.g. the script "()=>42".
  const std::pair<int, int> kTopLevelMarker = std::make_pair(-1, -1);
680 681 682 683
  std::map<std::pair<int, int>, FunctionLiteral*> position_to_new_literal;
  for (FunctionLiteral* literal : new_literals) {
    DCHECK(literal->start_position() != kNoSourcePosition);
    DCHECK(literal->end_position() != kNoSourcePosition);
684 685 686 687 688 689 690 691
    std::pair<int, int> key =
        literal->function_literal_id() == FunctionLiteral::kIdTypeTopLevel
            ? kTopLevelMarker
            : std::make_pair(literal->start_position(),
                             literal->end_position());
    // Make sure there are no duplicate keys.
    DCHECK_EQ(position_to_new_literal.find(key), position_to_new_literal.end());
    position_to_new_literal[key] = literal;
692 693 694 695 696 697
  }
  LiteralMap mappings;
  std::unordered_map<FunctionLiteral*, ChangeState> change_state;
  for (const auto& change_pair : changes) {
    FunctionLiteral* literal = change_pair.first;
    const FunctionLiteralChange& change = change_pair.second;
698 699 700 701 702 703
    std::pair<int, int> key =
        literal->function_literal_id() == FunctionLiteral::kIdTypeTopLevel
            ? kTopLevelMarker
            : std::make_pair(change.new_start_position,
                             change.new_end_position);
    auto it = position_to_new_literal.find(key);
704 705 706 707 708 709 710 711 712 713 714 715
    if (it == position_to_new_literal.end() ||
        HasChangedScope(literal, it->second)) {
      change_state[literal] = ChangeState::DAMAGED;
      if (!change.outer_literal) continue;
      if (change_state[change.outer_literal] != ChangeState::DAMAGED) {
        change_state[change.outer_literal] = ChangeState::CHANGED;
      }
    } else {
      mappings[literal] = it->second;
      if (change_state.find(literal) == change_state.end()) {
        change_state[literal] =
            change.has_changes ? ChangeState::CHANGED : ChangeState::UNCHANGED;
716
      }
717
    }
718
  }
719 720 721 722 723
  for (const auto& mapping : mappings) {
    if (change_state[mapping.first] == ChangeState::UNCHANGED) {
      (*unchanged)[mapping.first] = mapping.second;
    } else if (change_state[mapping.first] == ChangeState::CHANGED) {
      (*changed)[mapping.first] = mapping.second;
724
    }
725
  }
726
}
727

728 729 730 731 732 733 734 735 736 737 738 739 740 741
class CollectFunctionLiterals final
    : public AstTraversalVisitor<CollectFunctionLiterals> {
 public:
  CollectFunctionLiterals(Isolate* isolate, AstNode* root)
      : AstTraversalVisitor<CollectFunctionLiterals>(isolate, root) {}
  void VisitFunctionLiteral(FunctionLiteral* lit) {
    AstTraversalVisitor::VisitFunctionLiteral(lit);
    literals_->push_back(lit);
  }
  void Run(std::vector<FunctionLiteral*>* literals) {
    literals_ = literals;
    AstTraversalVisitor::Run();
    literals_ = nullptr;
  }
742

743 744 745
 private:
  std::vector<FunctionLiteral*>* literals_;
};
746

747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
bool ParseScript(Isolate* isolate, ParseInfo* parse_info, bool compile_as_well,
                 std::vector<FunctionLiteral*>* literals,
                 debug::LiveEditResult* result) {
  parse_info->set_eager();
  v8::TryCatch try_catch(reinterpret_cast<v8::Isolate*>(isolate));
  Handle<SharedFunctionInfo> shared;
  bool success = false;
  if (compile_as_well) {
    success =
        Compiler::CompileForLiveEdit(parse_info, isolate).ToHandle(&shared);
  } else {
    success = parsing::ParseProgram(parse_info, isolate);
    if (success) {
      success = Compiler::Analyze(parse_info);
      parse_info->ast_value_factory()->Internalize(isolate);
762
    }
763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797
  }
  if (!success) {
    isolate->OptionalRescheduleException(false);
    DCHECK(try_catch.HasCaught());
    result->message = try_catch.Message()->Get();
    auto self = Utils::OpenHandle(*try_catch.Message());
    auto msg = i::Handle<i::JSMessageObject>::cast(self);
    result->line_number = msg->GetLineNumber();
    result->column_number = msg->GetColumnNumber();
    result->status = debug::LiveEditResult::COMPILE_ERROR;
    return false;
  }
  CollectFunctionLiterals(isolate, parse_info->literal()).Run(literals);
  return true;
}

struct FunctionData {
  FunctionData(FunctionLiteral* literal, bool should_restart)
      : literal(literal),
        stack_position(NOT_ON_STACK),
        should_restart(should_restart) {}

  FunctionLiteral* literal;
  MaybeHandle<SharedFunctionInfo> shared;
  std::vector<Handle<JSFunction>> js_functions;
  std::vector<Handle<JSGeneratorObject>> running_generators;
  // In case of multiple functions with different stack position, the latest
  // one (in the order below) is used, since it is the most restrictive.
  // This is important only for functions to be restarted.
  enum StackPosition {
    NOT_ON_STACK,
    ABOVE_BREAK_FRAME,
    PATCHABLE,
    BELOW_NON_DROPPABLE_FRAME,
    ARCHIVED_THREAD,
798
  };
799 800
  StackPosition stack_position;
  bool should_restart;
801 802
};

803 804 805 806
class FunctionDataMap : public ThreadVisitor {
 public:
  void AddInterestingLiteral(int script_id, FunctionLiteral* literal,
                             bool should_restart) {
807
    map_.emplace(GetFuncId(script_id, literal),
808 809
                 FunctionData{literal, should_restart});
  }
810

811 812 813
  bool Lookup(SharedFunctionInfo* sfi, FunctionData** data) {
    int start_position = sfi->StartPosition();
    if (!sfi->script()->IsScript() || start_position == -1) {
814
      return false;
815
    }
816
    Script* script = Script::cast(sfi->script());
817
    return Lookup(GetFuncId(script->id(), sfi), data);
818 819 820 821
  }

  bool Lookup(Handle<Script> script, FunctionLiteral* literal,
              FunctionData** data) {
822
    return Lookup(GetFuncId(script->id(), literal), data);
823 824 825 826 827 828 829 830 831
  }

  void Fill(Isolate* isolate, Address* restart_frame_fp) {
    {
      HeapIterator iterator(isolate->heap(), HeapIterator::kFilterUnreachable);
      while (HeapObject* obj = iterator.next()) {
        if (obj->IsSharedFunctionInfo()) {
          SharedFunctionInfo* sfi = SharedFunctionInfo::cast(obj);
          FunctionData* data = nullptr;
832
          if (!Lookup(sfi, &data)) continue;
833 834 835 836 837
          data->shared = handle(sfi, isolate);
        } else if (obj->IsJSFunction()) {
          JSFunction* js_function = JSFunction::cast(obj);
          SharedFunctionInfo* sfi = js_function->shared();
          FunctionData* data = nullptr;
838
          if (!Lookup(sfi, &data)) continue;
839 840 841 842 843 844
          data->js_functions.emplace_back(js_function, isolate);
        } else if (obj->IsJSGeneratorObject()) {
          JSGeneratorObject* gen = JSGeneratorObject::cast(obj);
          if (gen->is_closed()) continue;
          SharedFunctionInfo* sfi = gen->function()->shared();
          FunctionData* data = nullptr;
845
          if (!Lookup(sfi, &data)) continue;
846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874
          data->running_generators.emplace_back(gen, isolate);
        }
      }
    }
    FunctionData::StackPosition stack_position =
        isolate->debug()->break_frame_id() == StackFrame::NO_ID
            ? FunctionData::PATCHABLE
            : FunctionData::ABOVE_BREAK_FRAME;
    for (StackFrameIterator it(isolate); !it.done(); it.Advance()) {
      StackFrame* frame = it.frame();
      if (stack_position == FunctionData::ABOVE_BREAK_FRAME) {
        if (frame->id() == isolate->debug()->break_frame_id()) {
          stack_position = FunctionData::PATCHABLE;
        }
      }
      if (stack_position == FunctionData::PATCHABLE &&
          (frame->is_exit() || frame->is_builtin_exit())) {
        stack_position = FunctionData::BELOW_NON_DROPPABLE_FRAME;
        continue;
      }
      if (!frame->is_java_script()) continue;
      std::vector<Handle<SharedFunctionInfo>> sfis;
      JavaScriptFrame::cast(frame)->GetFunctions(&sfis);
      for (auto& sfi : sfis) {
        if (stack_position == FunctionData::PATCHABLE &&
            IsResumableFunction(sfi->kind())) {
          stack_position = FunctionData::BELOW_NON_DROPPABLE_FRAME;
        }
        FunctionData* data = nullptr;
875
        if (!Lookup(*sfi, &data)) continue;
876 877 878 879
        if (!data->should_restart) continue;
        data->stack_position = stack_position;
        *restart_frame_fp = frame->fp();
      }
880
    }
881

882
    isolate->thread_manager()->IterateArchivedThreads(this);
883 884
  }

885
 private:
886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915
  // Unique id for a function: script_id + start_position, where start_position
  // is special cased to -1 for top-level so that it does not overlap with a
  // function whose start position is 0.
  using FuncId = std::pair<int, int>;

  FuncId GetFuncId(int script_id, FunctionLiteral* literal) {
    int start_position = literal->start_position();
    if (literal->function_literal_id() == 0) {
      // This is the top-level script function literal, so special case its
      // start position
      DCHECK_EQ(start_position, 0);
      start_position = -1;
    }
    return FuncId(script_id, start_position);
  }

  FuncId GetFuncId(int script_id, SharedFunctionInfo* sfi) {
    DCHECK_EQ(script_id, Script::cast(sfi->script())->id());
    int start_position = sfi->StartPosition();
    DCHECK_NE(start_position, -1);
    if (sfi->is_toplevel()) {
      // This is the top-level function, so special case its start position
      DCHECK_EQ(start_position, 0);
      start_position = -1;
    }
    return FuncId(script_id, start_position);
  }

  bool Lookup(FuncId id, FunctionData** data) {
    auto it = map_.find(id);
916 917 918 919 920 921 922 923 924 925 926
    if (it == map_.end()) return false;
    *data = &it->second;
    return true;
  }

  void VisitThread(Isolate* isolate, ThreadLocalTop* top) override {
    for (JavaScriptFrameIterator it(isolate, top); !it.done(); it.Advance()) {
      std::vector<Handle<SharedFunctionInfo>> sfis;
      it.frame()->GetFunctions(&sfis);
      for (auto& sfi : sfis) {
        FunctionData* data = nullptr;
927
        if (!Lookup(*sfi, &data)) continue;
928 929 930
        data->stack_position = FunctionData::ARCHIVED_THREAD;
      }
    }
931
  }
932

933
  std::map<FuncId, FunctionData> map_;
934
};
935

936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965
bool CanPatchScript(const LiteralMap& changed, Handle<Script> script,
                    Handle<Script> new_script,
                    FunctionDataMap& function_data_map,
                    debug::LiveEditResult* result) {
  debug::LiveEditResult::Status status = debug::LiveEditResult::OK;
  for (const auto& mapping : changed) {
    FunctionData* data = nullptr;
    function_data_map.Lookup(script, mapping.first, &data);
    FunctionData* new_data = nullptr;
    function_data_map.Lookup(new_script, mapping.second, &new_data);
    Handle<SharedFunctionInfo> sfi;
    if (!data->shared.ToHandle(&sfi)) {
      continue;
    } else if (!data->should_restart) {
      UNREACHABLE();
    } else if (data->stack_position == FunctionData::ABOVE_BREAK_FRAME) {
      status = debug::LiveEditResult::BLOCKED_BY_FUNCTION_ABOVE_BREAK_FRAME;
    } else if (data->stack_position ==
               FunctionData::BELOW_NON_DROPPABLE_FRAME) {
      status =
          debug::LiveEditResult::BLOCKED_BY_FUNCTION_BELOW_NON_DROPPABLE_FRAME;
    } else if (!data->running_generators.empty()) {
      status = debug::LiveEditResult::BLOCKED_BY_RUNNING_GENERATOR;
    } else if (data->stack_position == FunctionData::ARCHIVED_THREAD) {
      status = debug::LiveEditResult::BLOCKED_BY_ACTIVE_FUNCTION;
    }
    if (status != debug::LiveEditResult::OK) {
      result->status = status;
      return false;
    }
966
  }
967
  return true;
968
}
969

970 971 972 973 974 975 976 977 978
bool CanRestartFrame(Isolate* isolate, Address fp,
                     FunctionDataMap& function_data_map,
                     const LiteralMap& changed, debug::LiveEditResult* result) {
  DCHECK_GT(fp, 0);
  StackFrame* restart_frame = nullptr;
  StackFrameIterator it(isolate);
  for (; !it.done(); it.Advance()) {
    if (it.frame()->fp() == fp) {
      restart_frame = it.frame();
979 980
      break;
    }
981 982 983 984 985 986 987 988 989 990
  }
  DCHECK(restart_frame && restart_frame->is_java_script());
  if (!LiveEdit::kFrameDropperSupported) {
    result->status = debug::LiveEditResult::FRAME_RESTART_IS_NOT_SUPPORTED;
    return false;
  }
  std::vector<Handle<SharedFunctionInfo>> sfis;
  JavaScriptFrame::cast(restart_frame)->GetFunctions(&sfis);
  for (auto& sfi : sfis) {
    FunctionData* data = nullptr;
991
    if (!function_data_map.Lookup(*sfi, &data)) continue;
992 993 994 995 996 997 998 999 1000
    auto new_literal_it = changed.find(data->literal);
    if (new_literal_it == changed.end()) continue;
    if (new_literal_it->second->scope()->new_target_var()) {
      result->status =
          debug::LiveEditResult::BLOCKED_BY_NEW_TARGET_IN_RESTART_FRAME;
      return false;
    }
  }
  return true;
1001 1002
}

1003
void TranslateSourcePositionTable(Isolate* isolate, Handle<BytecodeArray> code,
1004
                                  const std::vector<SourceChangeRange>& diffs) {
1005
  SourcePositionTableBuilder builder;
1006

1007
  Handle<ByteArray> source_position_table(code->SourcePositionTable(), isolate);
1008
  for (SourcePositionTableIterator iterator(*source_position_table);
1009
       !iterator.done(); iterator.Advance()) {
1010 1011
    SourcePosition position = iterator.source_position();
    position.SetScriptOffset(
1012
        LiveEdit::TranslatePosition(diffs, position.ScriptOffset()));
1013
    builder.AddPosition(iterator.code_offset(), position,
1014 1015 1016
                        iterator.is_statement());
  }

1017
  Handle<ByteArray> new_source_position_table(
1018
      builder.ToSourcePositionTable(isolate));
1019
  code->set_source_position_table(*new_source_position_table);
1020
  LOG_CODE_EVENT(isolate,
1021
                 CodeLinePosInfoRecordEvent(code->GetFirstBytecodeAddress(),
1022
                                            *new_source_position_table));
1023
}
1024

1025 1026 1027 1028 1029 1030 1031 1032
void UpdatePositions(Isolate* isolate, Handle<SharedFunctionInfo> sfi,
                     const std::vector<SourceChangeRange>& diffs) {
  int old_start_position = sfi->StartPosition();
  int new_start_position =
      LiveEdit::TranslatePosition(diffs, old_start_position);
  int new_end_position = LiveEdit::TranslatePosition(diffs, sfi->EndPosition());
  int new_function_token_position =
      LiveEdit::TranslatePosition(diffs, sfi->function_token_position());
1033 1034 1035
  sfi->SetPosition(new_start_position, new_end_position);
  sfi->SetFunctionTokenPosition(new_function_token_position,
                                new_start_position);
1036
  if (sfi->HasBytecodeArray()) {
1037 1038
    TranslateSourcePositionTable(
        isolate, handle(sfi->GetBytecodeArray(), isolate), diffs);
1039
  }
1040
}
1041
}  // anonymous namespace
1042

1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
void LiveEdit::PatchScript(Isolate* isolate, Handle<Script> script,
                           Handle<String> new_source, bool preview,
                           debug::LiveEditResult* result) {
  std::vector<SourceChangeRange> diffs;
  LiveEdit::CompareStrings(isolate,
                           handle(String::cast(script->source()), isolate),
                           new_source, &diffs);
  if (diffs.empty()) {
    result->status = debug::LiveEditResult::OK;
    return;
1053 1054
  }

1055 1056 1057
  ParseInfo parse_info(isolate, script);
  std::vector<FunctionLiteral*> literals;
  if (!ParseScript(isolate, &parse_info, false, &literals, result)) return;
1058

1059 1060 1061 1062 1063 1064
  Handle<Script> new_script = isolate->factory()->CloneScript(script);
  new_script->set_source(*new_source);
  std::vector<FunctionLiteral*> new_literals;
  ParseInfo new_parse_info(isolate, new_script);
  if (!ParseScript(isolate, &new_parse_info, true, &new_literals, result)) {
    return;
1065
  }
1066

1067 1068
  FunctionLiteralChanges literal_changes;
  CalculateFunctionLiteralChanges(literals, diffs, &literal_changes);
1069

1070 1071 1072
  LiteralMap changed;
  LiteralMap unchanged;
  MapLiterals(literal_changes, new_literals, &unchanged, &changed);
1073

1074 1075 1076 1077 1078
  FunctionDataMap function_data_map;
  for (const auto& mapping : changed) {
    function_data_map.AddInterestingLiteral(script->id(), mapping.first, true);
    function_data_map.AddInterestingLiteral(new_script->id(), mapping.second,
                                            false);
1079
  }
1080 1081
  for (const auto& mapping : unchanged) {
    function_data_map.AddInterestingLiteral(script->id(), mapping.first, false);
1082
  }
1083 1084
  Address restart_frame_fp = 0;
  function_data_map.Fill(isolate, &restart_frame_fp);
1085

1086 1087 1088 1089 1090 1091 1092
  if (!CanPatchScript(changed, script, new_script, function_data_map, result)) {
    return;
  }
  if (restart_frame_fp &&
      !CanRestartFrame(isolate, restart_frame_fp, function_data_map, changed,
                       result)) {
    return;
1093
  }
1094

1095 1096 1097 1098
  if (preview) {
    result->status = debug::LiveEditResult::OK;
    return;
  }
1099

1100
  std::map<int, int> start_position_to_unchanged_id;
1101 1102 1103 1104 1105
  for (const auto& mapping : unchanged) {
    FunctionData* data = nullptr;
    if (!function_data_map.Lookup(script, mapping.first, &data)) continue;
    Handle<SharedFunctionInfo> sfi;
    if (!data->shared.ToHandle(&sfi)) continue;
1106
    DCHECK_EQ(sfi->script(), *script);
1107

1108 1109 1110 1111 1112
    isolate->compilation_cache()->Remove(sfi);
    isolate->debug()->DeoptimizeFunction(sfi);
    if (sfi->HasDebugInfo()) {
      Handle<DebugInfo> debug_info(sfi->GetDebugInfo(), isolate);
      isolate->debug()->RemoveBreakInfoAndMaybeFree(debug_info);
1113
    }
1114
    UpdatePositions(isolate, sfi, diffs);
1115

1116
    sfi->set_script(*new_script);
1117 1118 1119 1120
    if (sfi->HasUncompiledData()) {
      sfi->uncompiled_data()->set_function_literal_id(
          mapping.second->function_literal_id());
    }
1121 1122
    new_script->shared_function_infos()->Set(
        mapping.second->function_literal_id(), HeapObjectReference::Weak(*sfi));
1123
    DCHECK_EQ(sfi->FunctionLiteralId(isolate),
1124 1125
              mapping.second->function_literal_id());

1126 1127 1128 1129
    // Save the new start_position -> id mapping, so that we can recover it when
    // iterating over changed functions' constant pools.
    start_position_to_unchanged_id[mapping.second->start_position()] =
        mapping.second->function_literal_id();
1130

1131 1132 1133
    if (sfi->HasUncompiledDataWithPreParsedScope()) {
      sfi->ClearPreParsedScopeData();
    }
1134

1135 1136 1137 1138
    for (auto& js_function : data->js_functions) {
      js_function->set_feedback_cell(*isolate->factory()->many_closures_cell());
      if (!js_function->is_compiled()) continue;
      JSFunction::EnsureFeedbackVector(js_function);
1139
    }
1140

1141
    if (!sfi->HasBytecodeArray()) continue;
1142
    FixedArray* constants = sfi->GetBytecodeArray()->constant_pool();
1143 1144 1145
    for (int i = 0; i < constants->length(); ++i) {
      if (!constants->get(i)->IsSharedFunctionInfo()) continue;
      FunctionData* data = nullptr;
1146 1147
      if (!function_data_map.Lookup(SharedFunctionInfo::cast(constants->get(i)),
                                    &data)) {
1148
        continue;
1149
      }
1150 1151 1152 1153 1154 1155 1156 1157
      auto change_it = changed.find(data->literal);
      if (change_it == changed.end()) continue;
      if (!function_data_map.Lookup(new_script, change_it->second, &data)) {
        continue;
      }
      Handle<SharedFunctionInfo> new_sfi;
      if (!data->shared.ToHandle(&new_sfi)) continue;
      constants->set(i, *new_sfi);
1158 1159
    }
  }
1160 1161 1162 1163
  for (const auto& mapping : changed) {
    FunctionData* data = nullptr;
    if (!function_data_map.Lookup(new_script, mapping.second, &data)) continue;
    Handle<SharedFunctionInfo> new_sfi = data->shared.ToHandleChecked();
1164
    DCHECK_EQ(new_sfi->script(), *new_script);
1165

1166 1167 1168
    if (!function_data_map.Lookup(script, mapping.first, &data)) continue;
    Handle<SharedFunctionInfo> sfi;
    if (!data->shared.ToHandle(&sfi)) continue;
1169

1170 1171 1172 1173 1174
    isolate->debug()->DeoptimizeFunction(sfi);
    isolate->compilation_cache()->Remove(sfi);
    for (auto& js_function : data->js_functions) {
      js_function->set_shared(*new_sfi);
      js_function->set_code(js_function->shared()->GetCode());
1175

1176 1177 1178
      js_function->set_feedback_cell(*isolate->factory()->many_closures_cell());
      if (!js_function->is_compiled()) continue;
      JSFunction::EnsureFeedbackVector(js_function);
1179
    }
1180 1181 1182 1183 1184
  }
  SharedFunctionInfo::ScriptIterator it(isolate, *new_script);
  while (SharedFunctionInfo* sfi = it.Next()) {
    if (!sfi->HasBytecodeArray()) continue;
    FixedArray* constants = sfi->GetBytecodeArray()->constant_pool();
1185 1186 1187 1188
    for (int i = 0; i < constants->length(); ++i) {
      if (!constants->get(i)->IsSharedFunctionInfo()) continue;
      SharedFunctionInfo* inner_sfi =
          SharedFunctionInfo::cast(constants->get(i));
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200
      // See if there is a mapping from this function's start position to a
      // unchanged function's id.
      auto unchanged_it =
          start_position_to_unchanged_id.find(inner_sfi->StartPosition());
      if (unchanged_it == start_position_to_unchanged_id.end()) continue;

      // Grab that function id from the new script's SFI list, which should have
      // already been updated in in the unchanged pass.
      SharedFunctionInfo* old_unchanged_inner_sfi =
          SharedFunctionInfo::cast(new_script->shared_function_infos()
                                       ->Get(unchanged_it->second)
                                       ->GetHeapObject());
1201
      if (old_unchanged_inner_sfi == inner_sfi) continue;
1202
      DCHECK_NE(old_unchanged_inner_sfi, inner_sfi);
1203 1204
      // Now some sanity checks. Make sure that the unchanged SFI has already
      // been processed and patched to be on the new script ...
1205
      DCHECK_EQ(old_unchanged_inner_sfi->script(), *new_script);
1206
      constants->set(i, old_unchanged_inner_sfi);
1207 1208 1209 1210
    }
  }
#ifdef DEBUG
  {
1211 1212 1213
    // Check that all the functions in the new script are valid, that their
    // function literals match what is expected, and that start positions are
    // unique.
1214 1215
    DisallowHeapAllocation no_gc;

1216
    SharedFunctionInfo::ScriptIterator it(isolate, *new_script);
1217
    std::set<int> start_positions;
1218 1219
    while (SharedFunctionInfo* sfi = it.Next()) {
      DCHECK_EQ(sfi->script(), *new_script);
1220
      DCHECK_EQ(sfi->FunctionLiteralId(isolate), it.CurrentIndex());
1221 1222 1223 1224 1225 1226 1227
      // Don't check the start position of the top-level function, as it can
      // overlap with a function in the script.
      if (sfi->is_toplevel()) {
        DCHECK_EQ(start_positions.find(sfi->StartPosition()),
                  start_positions.end());
        start_positions.insert(sfi->StartPosition());
      }
1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239

      if (!sfi->HasBytecodeArray()) continue;
      // Check that all the functions in this function's constant pool are also
      // on the new script, and that their id matches their index in the new
      // scripts function list.
      FixedArray* constants = sfi->GetBytecodeArray()->constant_pool();
      for (int i = 0; i < constants->length(); ++i) {
        if (!constants->get(i)->IsSharedFunctionInfo()) continue;
        SharedFunctionInfo* inner_sfi =
            SharedFunctionInfo::cast(constants->get(i));
        DCHECK_EQ(inner_sfi->script(), *new_script);
        DCHECK_EQ(inner_sfi, new_script->shared_function_infos()
1240
                                 ->Get(inner_sfi->FunctionLiteralId(isolate))
1241 1242 1243
                                 ->GetHeapObject());
      }
    }
1244
  }
1245
#endif
1246

1247 1248 1249 1250 1251 1252
  if (restart_frame_fp) {
    for (StackFrameIterator it(isolate); !it.done(); it.Advance()) {
      if (it.frame()->fp() == restart_frame_fp) {
        isolate->debug()->ScheduleFrameRestart(it.frame());
        result->stack_changed = true;
        break;
1253 1254 1255 1256
      }
    }
  }

1257 1258 1259 1260 1261
  int script_id = script->id();
  script->set_id(new_script->id());
  new_script->set_id(script_id);
  result->status = debug::LiveEditResult::OK;
  result->script = ToApiHandle<v8::debug::Script>(new_script);
1262 1263
}

1264 1265
void LiveEdit::InitializeThreadLocal(Debug* debug) {
  debug->thread_local_.restart_fp_ = 0;
1266 1267
}

1268 1269 1270 1271 1272
bool LiveEdit::RestartFrame(JavaScriptFrame* frame) {
  if (!LiveEdit::kFrameDropperSupported) return false;
  Isolate* isolate = frame->isolate();
  StackFrame::Id break_frame_id = isolate->debug()->break_frame_id();
  bool break_frame_found = break_frame_id == StackFrame::NO_ID;
1273 1274
  for (StackFrameIterator it(isolate); !it.done(); it.Advance()) {
    StackFrame* current = it.frame();
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294
    break_frame_found = break_frame_found || break_frame_id == current->id();
    if (current->fp() == frame->fp()) {
      if (break_frame_found) {
        isolate->debug()->ScheduleFrameRestart(current);
        return true;
      } else {
        return false;
      }
    }
    if (!break_frame_found) continue;
    if (current->is_exit() || current->is_builtin_exit()) {
      return false;
    }
    if (!current->is_java_script()) continue;
    std::vector<Handle<SharedFunctionInfo>> shareds;
    JavaScriptFrame::cast(current)->GetFunctions(&shareds);
    for (auto& shared : shareds) {
      if (IsResumableFunction(shared->kind())) {
        return false;
      }
1295
    }
1296
  }
1297
  return false;
1298 1299
}

1300 1301
void LiveEdit::CompareStrings(Isolate* isolate, Handle<String> s1,
                              Handle<String> s2,
1302
                              std::vector<SourceChangeRange>* diffs) {
1303 1304
  s1 = String::Flatten(isolate, s1);
  s2 = String::Flatten(isolate, s2);
1305

1306 1307
  LineEndsWrapper line_ends1(isolate, s1);
  LineEndsWrapper line_ends2(isolate, s2);
1308 1309 1310

  LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
  TokenizingLineArrayCompareOutput output(isolate, line_ends1, line_ends2, s1,
1311
                                          s2, diffs);
1312 1313 1314 1315 1316 1317

  NarrowDownInput(&input, &output);

  Comparator::CalculateDifference(&input, &output);
}

1318
int LiveEdit::TranslatePosition(const std::vector<SourceChangeRange>& diffs,
1319
                                int position) {
1320
  auto it = std::lower_bound(diffs.begin(), diffs.end(), position,
1321 1322 1323
                             [](const SourceChangeRange& change, int position) {
                               return change.end_position < position;
                             });
1324
  if (it != diffs.end() && position == it->end_position) {
1325 1326
    return it->new_end_position;
  }
1327 1328
  if (it == diffs.begin()) return position;
  DCHECK(it == diffs.end() || position <= it->start_position);
1329 1330 1331
  it = std::prev(it);
  return position + (it->new_end_position - it->end_position);
}
1332 1333
}  // namespace internal
}  // namespace v8