liveedit.cc 39.1 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/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 13
#include "src/codegen/compilation-cache.h"
#include "src/codegen/compiler.h"
#include "src/codegen/source-position-table.h"
14
#include "src/common/globals.h"
15
#include "src/debug/debug-interface.h"
16
#include "src/debug/debug-stack-trace-iterator.h"
17
#include "src/debug/debug.h"
18
#include "src/debug/liveedit-diff.h"
19
#include "src/execution/frames-inl.h"
20
#include "src/execution/v8threads.h"
21
#include "src/logging/log.h"
22
#include "src/objects/js-generator-inl.h"
23
#include "src/objects/objects-inl.h"
24 25
#include "src/parsing/parse-info.h"
#include "src/parsing/parsing.h"
26 27 28

namespace v8 {
namespace internal {
29
namespace {
30

31 32
bool CompareSubstrings(Handle<String> s1, int pos1, Handle<String> s2, int pos2,
                       int len) {
33
  for (int i = 0; i < len; i++) {
34
    if (s1->Get(i + pos1) != s2->Get(i + pos2)) return false;
35 36 37 38
  }
  return true;
}

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
// 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.
58
void NarrowDownInput(SubrangableInput* input, SubrangableOutput* output) {
59 60 61 62 63 64 65 66
  const int len1 = input->GetLength1();
  const int len2 = input->GetLength2();

  int common_prefix_len;
  int common_suffix_len;

  {
    common_prefix_len = 0;
67
    int prefix_limit = std::min(len1, len2);
68 69 70 71 72 73
    while (common_prefix_len < prefix_limit &&
        input->Equals(common_prefix_len, common_prefix_len)) {
      common_prefix_len++;
    }

    common_suffix_len = 0;
74 75
    int suffix_limit =
        std::min(len1 - common_prefix_len, len2 - common_prefix_len);
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

    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);
  }
}

96 97 98 99 100 101 102 103 104 105
// 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) {
  }
106 107 108
  int GetLength1() override { return len1_; }
  int GetLength2() override { return len2_; }
  bool Equals(int index1, int index2) override {
109 110 111 112 113 114 115 116 117 118 119 120
    return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
  }

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

121
// Stores compare result in std::vector. Converts substring positions
122 123 124
// to absolute positions.
class TokensCompareOutput : public Comparator::Output {
 public:
125 126 127
  TokensCompareOutput(int offset1, int offset2,
                      std::vector<SourceChangeRange>* output)
      : output_(output), offset1_(offset1), offset2_(offset2) {}
128

129 130 131 132
  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});
133 134 135
  }

 private:
136
  std::vector<SourceChangeRange>* output_;
137 138 139 140
  int offset1_;
  int offset2_;
};

141 142 143 144
// 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:
145 146 147
  explicit LineEndsWrapper(Isolate* isolate, Handle<String> string)
      : ends_array_(String::CalculateLineEnds(isolate, string, false)),
        string_len_(string->length()) {}
148 149 150 151 152
  int length() {
    return ends_array_->length() + 1;
  }
  // Returns start for any line including start of the imaginary line after
  // the last line.
153
  int GetLineStart(int index) { return index == 0 ? 0 : GetLineEnd(index - 1); }
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
  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
170
    return Smi::ToInt(ends_array_->get(index)) + 1;
171 172 173 174
  }
};

// Represents 2 strings as 2 arrays of lines.
175
class LineArrayCompareInput : public SubrangableInput {
176
 public:
177
  LineArrayCompareInput(Handle<String> s1, Handle<String> s2,
178
                        LineEndsWrapper line_ends1, LineEndsWrapper line_ends2)
179
      : s1_(s1), s2_(s2), line_ends1_(line_ends1),
180 181 182 183
        line_ends2_(line_ends2),
        subrange_offset1_(0), subrange_offset2_(0),
        subrange_len1_(line_ends1_.length()),
        subrange_len2_(line_ends2_.length()) {
184
  }
185 186 187
  int GetLength1() override { return subrange_len1_; }
  int GetLength2() override { return subrange_len2_; }
  bool Equals(int index1, int index2) override {
188 189 190
    index1 += subrange_offset1_;
    index2 += subrange_offset2_;

191 192 193 194 195 196 197 198 199
    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;
    }
200
    return CompareSubstrings(s1_, line_start1, s2_, line_start2,
201
                             len1);
202
  }
203
  void SetSubrange1(int offset, int len) override {
204 205 206
    subrange_offset1_ = offset;
    subrange_len1_ = len;
  }
207
  void SetSubrange2(int offset, int len) override {
208 209 210
    subrange_offset2_ = offset;
    subrange_len2_ = len;
  }
211 212 213 214 215 216

 private:
  Handle<String> s1_;
  Handle<String> s2_;
  LineEndsWrapper line_ends1_;
  LineEndsWrapper line_ends2_;
217 218 219 220
  int subrange_offset1_;
  int subrange_offset2_;
  int subrange_len1_;
  int subrange_len2_;
221 222
};

223
// Stores compare result in std::vector. For each chunk tries to conduct
224
// a fine-grained nested diff token-wise.
225
class TokenizingLineArrayCompareOutput : public SubrangableOutput {
226
 public:
227
  TokenizingLineArrayCompareOutput(Isolate* isolate, LineEndsWrapper line_ends1,
228
                                   LineEndsWrapper line_ends2,
229 230
                                   Handle<String> s1, Handle<String> s2,
                                   std::vector<SourceChangeRange>* output)
231 232 233 234 235 236
      : isolate_(isolate),
        line_ends1_(line_ends1),
        line_ends2_(line_ends2),
        s1_(s1),
        s2_(s2),
        subrange_offset1_(0),
237 238
        subrange_offset2_(0),
        output_(output) {}
239

240 241
  void AddChunk(int line_pos1, int line_pos2, int line_len1,
                int line_len2) override {
242 243 244
    line_pos1 += subrange_offset1_;
    line_pos2 += subrange_offset2_;

245 246 247 248 249
    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;

250 251
    if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
      // Chunk is small enough to conduct a nested token-level diff.
252
      HandleScope subTaskScope(isolate_);
253 254 255

      TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
                                      s2_, char_pos2, char_len2);
256
      TokensCompareOutput tokens_output(char_pos1, char_pos2, output_);
257

258
      Comparator::CalculateDifference(&tokens_input, &tokens_output);
259
    } else {
260 261
      output_->emplace_back(SourceChangeRange{
          char_pos1, char_pos1 + char_len1, char_pos2, char_pos2 + char_len2});
262
    }
263
  }
264
  void SetSubrange1(int offset, int len) override {
265 266
    subrange_offset1_ = offset;
  }
267
  void SetSubrange2(int offset, int len) override {
268 269
    subrange_offset2_ = offset;
  }
270 271

 private:
272 273
  static const int CHUNK_LEN_LIMIT = 800;

274
  Isolate* isolate_;
275 276
  LineEndsWrapper line_ends1_;
  LineEndsWrapper line_ends2_;
277 278
  Handle<String> s1_;
  Handle<String> s2_;
279 280
  int subrange_offset1_;
  int subrange_offset2_;
281
  std::vector<SourceChangeRange>* output_;
282
};
283

284 285
struct SourcePositionEvent {
  enum Type { LITERAL_STARTS, LITERAL_ENDS, DIFF_STARTS, DIFF_ENDS };
286

287 288
  int position;
  Type type;
289

290 291 292 293
  union {
    FunctionLiteral* literal;
    int pos_diff;
  };
294

295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
  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) {
311 312 313 314 315 316 317 318 319
      // 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();
320
    } else if (a.type == LITERAL_ENDS && b.type == LITERAL_ENDS) {
321 322 323 324 325 326 327 328 329
      // 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();
330 331
    } else {
      return a.pos_diff < b.pos_diff;
332 333
    }
  }
334
};
335

336 337 338 339 340 341 342 343 344 345 346 347 348 349
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) {}
};
350

351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
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;
    }
408
  }
409
}
410

411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
// 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;
429
      if (*it->second != *var->name()) return true;
430
    }
431 432
    scope_a = scope_a->outer_scope();
    scope_b = scope_b->outer_scope();
433
  }
434 435
  return scope_a != scope_b;
}
436

437 438 439 440 441 442
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) {
443 444 445
  // 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);
446 447 448 449
  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);
450
    std::pair<int, int> key =
451
        literal->function_literal_id() == kFunctionLiteralIdTopLevel
452 453 454 455 456 457
            ? 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;
458 459 460 461 462 463
  }
  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;
464
    std::pair<int, int> key =
465
        literal->function_literal_id() == kFunctionLiteralIdTopLevel
466 467 468 469
            ? kTopLevelMarker
            : std::make_pair(change.new_start_position,
                             change.new_end_position);
    auto it = position_to_new_literal.find(key);
470 471 472 473 474 475 476 477 478 479 480 481
    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;
482
      }
483
    }
484
  }
485 486 487 488 489
  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;
490
    }
491
  }
492
}
493

494 495 496 497 498 499 500 501 502 503 504 505 506 507
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;
  }
508

509 510 511
 private:
  std::vector<FunctionLiteral*>* literals_;
};
512

513 514
bool ParseScript(Isolate* isolate, Handle<Script> script, ParseInfo* parse_info,
                 bool compile_as_well, std::vector<FunctionLiteral*>* literals,
515 516 517 518 519
                 debug::LiveEditResult* result) {
  v8::TryCatch try_catch(reinterpret_cast<v8::Isolate*>(isolate));
  Handle<SharedFunctionInfo> shared;
  bool success = false;
  if (compile_as_well) {
520 521
    success = Compiler::CompileForLiveEdit(parse_info, script, isolate)
                  .ToHandle(&shared);
522
  } else {
523 524 525 526 527 528 529 530
    success = parsing::ParseProgram(parse_info, script, isolate,
                                    parsing::ReportStatisticsMode::kYes);
    if (!success) {
      // Throw the parser error.
      parse_info->pending_error_handler()->PrepareErrors(
          isolate, parse_info->ast_value_factory());
      parse_info->pending_error_handler()->ReportErrors(isolate, script);
    }
531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547
  }
  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 {
548 549
  explicit FunctionData(FunctionLiteral* literal)
      : literal(literal), stack_position(NOT_ON_STACK) {}
550 551 552 553 554 555 556 557

  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.
558
  enum StackPosition { NOT_ON_STACK, ON_TOP_ONLY, ON_STACK };
559
  StackPosition stack_position;
560 561
};

562 563
class FunctionDataMap : public ThreadVisitor {
 public:
564 565
  void AddInterestingLiteral(int script_id, FunctionLiteral* literal) {
    map_.emplace(GetFuncId(script_id, literal), FunctionData{literal});
566
  }
567

568
  bool Lookup(SharedFunctionInfo sfi, FunctionData** data) {
569 570
    int start_position = sfi.StartPosition();
    if (!sfi.script().IsScript() || start_position == -1) {
571
      return false;
572
    }
573 574
    Script script = Script::cast(sfi.script());
    return Lookup(GetFuncId(script.id(), sfi), data);
575 576 577 578
  }

  bool Lookup(Handle<Script> script, FunctionLiteral* literal,
              FunctionData** data) {
579
    return Lookup(GetFuncId(script->id(), literal), data);
580 581
  }

582
  void Fill(Isolate* isolate) {
583
    {
584 585
      HeapObjectIterator iterator(isolate->heap(),
                                  HeapObjectIterator::kFilterUnreachable);
586 587
      for (HeapObject obj = iterator.Next(); !obj.is_null();
           obj = iterator.Next()) {
588
        if (obj.IsSharedFunctionInfo()) {
589
          SharedFunctionInfo sfi = SharedFunctionInfo::cast(obj);
590
          FunctionData* data = nullptr;
591
          if (!Lookup(sfi, &data)) continue;
592
          data->shared = handle(sfi, isolate);
593
        } else if (obj.IsJSFunction()) {
594
          JSFunction js_function = JSFunction::cast(obj);
595
          SharedFunctionInfo sfi = js_function.shared();
596
          FunctionData* data = nullptr;
597
          if (!Lookup(sfi, &data)) continue;
598
          data->js_functions.emplace_back(js_function, isolate);
599
        } else if (obj.IsJSGeneratorObject()) {
600
          JSGeneratorObject gen = JSGeneratorObject::cast(obj);
601 602
          if (gen.is_closed()) continue;
          SharedFunctionInfo sfi = gen.function().shared();
603
          FunctionData* data = nullptr;
604
          if (!Lookup(sfi, &data)) continue;
605 606 607 608
          data->running_generators.emplace_back(gen, isolate);
        }
      }
    }
609

610
    // Visit the current thread stack.
611
    VisitCurrentThread(isolate);
612 613

    // Visit the stacks of all archived threads.
614
    isolate->thread_manager()->IterateArchivedThreads(this);
615 616
  }

617
 private:
618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633
  // 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);
  }

634
  FuncId GetFuncId(int script_id, SharedFunctionInfo sfi) {
635 636
    DCHECK_EQ(script_id, Script::cast(sfi.script()).id());
    int start_position = sfi.StartPosition();
637
    DCHECK_NE(start_position, -1);
638
    if (sfi.is_toplevel()) {
639 640 641 642 643 644 645 646 647
      // 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);
648 649 650 651 652 653 654 655 656 657 658
    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;
659
        if (!Lookup(*sfi, &data)) continue;
660
        data->stack_position = FunctionData::ON_STACK;
661 662
      }
    }
663
  }
664

665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
  void VisitCurrentThread(Isolate* isolate) {
    // We allow live editing the function that's currently top-of-stack. But
    // only if no activation of that function is anywhere else on the stack.
    bool is_top = true;
    for (DebugStackTraceIterator it(isolate, /* index */ 0); !it.Done();
         it.Advance(), is_top = false) {
      auto sfi = it.GetSharedFunctionInfo();
      if (sfi.is_null()) continue;
      FunctionData* data = nullptr;
      if (!Lookup(*sfi, &data)) continue;

      // ON_TOP_ONLY will only be set on the first iteration (and if the frame
      // can be restarted). Further activations will change the ON_TOP_ONLY to
      // ON_STACK and prevent the live edit from happening.
      data->stack_position = is_top && it.CanBeRestarted()
                                 ? FunctionData::ON_TOP_ONLY
                                 : FunctionData::ON_STACK;
    }
  }

685
  std::map<FuncId, FunctionData> map_;
686
};
687

688 689 690
bool CanPatchScript(const LiteralMap& changed, Handle<Script> script,
                    Handle<Script> new_script,
                    FunctionDataMap& function_data_map,
691
                    bool allow_top_frame_live_editing,
692
                    debug::LiveEditResult* result) {
693 694 695 696 697 698 699 700
  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;
701 702
    } else if (data->stack_position == FunctionData::ON_STACK) {
      result->status = debug::LiveEditResult::BLOCKED_BY_ACTIVE_FUNCTION;
703
      return false;
704 705
    } else if (!data->running_generators.empty()) {
      result->status = debug::LiveEditResult::BLOCKED_BY_RUNNING_GENERATOR;
706
      return false;
707 708 709 710 711 712
    } else if (data->stack_position == FunctionData::ON_TOP_ONLY) {
      if (!allow_top_frame_live_editing) {
        result->status = debug::LiveEditResult::BLOCKED_BY_ACTIVE_FUNCTION;
        return false;
      }
      result->restart_top_frame_required = true;
713 714 715
    }
  }
  return true;
716 717
}

718
void TranslateSourcePositionTable(Isolate* isolate, Handle<BytecodeArray> code,
719
                                  const std::vector<SourceChangeRange>& diffs) {
720 721
  Zone zone(isolate->allocator(), ZONE_NAME);
  SourcePositionTableBuilder builder(&zone);
722

723
  Handle<ByteArray> source_position_table(code->SourcePositionTable(), isolate);
724
  for (SourcePositionTableIterator iterator(*source_position_table);
725
       !iterator.done(); iterator.Advance()) {
726 727
    SourcePosition position = iterator.source_position();
    position.SetScriptOffset(
728
        LiveEdit::TranslatePosition(diffs, position.ScriptOffset()));
729
    builder.AddPosition(iterator.code_offset(), position,
730 731 732
                        iterator.is_statement());
  }

733
  Handle<ByteArray> new_source_position_table(
734
      builder.ToSourcePositionTable(isolate));
735
  code->set_source_position_table(*new_source_position_table, kReleaseStore);
736
  LOG_CODE_EVENT(isolate,
737
                 CodeLinePosInfoRecordEvent(code->GetFirstBytecodeAddress(),
738 739
                                            *new_source_position_table,
                                            JitCodeEvent::BYTE_CODE));
740
}
741

742 743 744 745 746 747 748 749
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());
750 751 752
  sfi->SetPosition(new_start_position, new_end_position);
  sfi->SetFunctionTokenPosition(new_function_token_position,
                                new_start_position);
753
  if (sfi->HasBytecodeArray()) {
754
    TranslateSourcePositionTable(
755
        isolate, handle(sfi->GetBytecodeArray(isolate), isolate), diffs);
756
  }
757
}
758
}  // anonymous namespace
759

760 761
void LiveEdit::PatchScript(Isolate* isolate, Handle<Script> script,
                           Handle<String> new_source, bool preview,
762
                           bool allow_top_frame_live_editing_param,
763 764 765 766 767 768 769 770
                           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;
771 772
  }

773 774 775
  ReusableUnoptimizedCompileState reusable_state(isolate);

  UnoptimizedCompileState compile_state;
776 777 778
  UnoptimizedCompileFlags flags =
      UnoptimizedCompileFlags::ForScriptCompile(isolate, *script);
  flags.set_is_eager(true);
779
  flags.set_is_reparse(true);
780
  ParseInfo parse_info(isolate, flags, &compile_state, &reusable_state);
781
  std::vector<FunctionLiteral*> literals;
782 783
  if (!ParseScript(isolate, script, &parse_info, false, &literals, result))
    return;
784

785 786
  Handle<Script> new_script = isolate->factory()->CloneScript(script);
  new_script->set_source(*new_source);
787
  UnoptimizedCompileState new_compile_state;
788 789 790
  UnoptimizedCompileFlags new_flags =
      UnoptimizedCompileFlags::ForScriptCompile(isolate, *new_script);
  new_flags.set_is_eager(true);
791 792
  ParseInfo new_parse_info(isolate, new_flags, &new_compile_state,
                           &reusable_state);
793
  std::vector<FunctionLiteral*> new_literals;
794 795
  if (!ParseScript(isolate, new_script, &new_parse_info, true, &new_literals,
                   result)) {
796
    return;
797
  }
798

799 800
  FunctionLiteralChanges literal_changes;
  CalculateFunctionLiteralChanges(literals, diffs, &literal_changes);
801

802 803 804
  LiteralMap changed;
  LiteralMap unchanged;
  MapLiterals(literal_changes, new_literals, &unchanged, &changed);
805

806 807
  FunctionDataMap function_data_map;
  for (const auto& mapping : changed) {
808 809
    function_data_map.AddInterestingLiteral(script->id(), mapping.first);
    function_data_map.AddInterestingLiteral(new_script->id(), mapping.second);
810
  }
811
  for (const auto& mapping : unchanged) {
812
    function_data_map.AddInterestingLiteral(script->id(), mapping.first);
813
  }
814
  function_data_map.Fill(isolate);
815

816 817 818 819
  const bool allow_top_frame_live_editing =
      allow_top_frame_live_editing_param && FLAG_live_edit_top_frame;
  if (!CanPatchScript(changed, script, new_script, function_data_map,
                      allow_top_frame_live_editing, result)) {
820 821
    return;
  }
822

823 824 825 826
  if (preview) {
    result->status = debug::LiveEditResult::OK;
    return;
  }
827

828 829 830 831 832 833 834
  // Patching a script means that the bytecode on the stack may no longer
  // correspond to the bytecode of the JSFunction for that frame. As a result
  // it is no longer safe to flush bytecode since we might flush the new
  // bytecode for a JSFunction that is on the stack with an old bytecode, which
  // breaks the invariant that any JSFunction active on the stack is compiled.
  isolate->set_disable_bytecode_flushing(true);

835
  std::map<int, int> start_position_to_unchanged_id;
836 837 838 839 840
  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;
841
    DCHECK_EQ(sfi->script(), *script);
842

843 844 845 846 847
    isolate->compilation_cache()->Remove(sfi);
    isolate->debug()->DeoptimizeFunction(sfi);
    if (sfi->HasDebugInfo()) {
      Handle<DebugInfo> debug_info(sfi->GetDebugInfo(), isolate);
      isolate->debug()->RemoveBreakInfoAndMaybeFree(debug_info);
848
    }
849
    SharedFunctionInfo::EnsureSourcePositionsAvailable(isolate, sfi);
850
    UpdatePositions(isolate, sfi, diffs);
851

852
    sfi->set_script(*new_script);
853
    sfi->set_function_literal_id(mapping.second->function_literal_id());
854
    new_script->shared_function_infos().Set(
855
        mapping.second->function_literal_id(), HeapObjectReference::Weak(*sfi));
856 857
    DCHECK_EQ(sfi->function_literal_id(),
              mapping.second->function_literal_id());
858

859 860 861 862
    // 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();
863

864 865
    if (sfi->HasUncompiledDataWithPreparseData()) {
      sfi->ClearPreparseData();
866
    }
867

868
    for (auto& js_function : data->js_functions) {
869 870
      js_function->set_raw_feedback_cell(
          *isolate->factory()->many_closures_cell());
871
      if (!js_function->is_compiled()) continue;
872
      IsCompiledScope is_compiled_scope(
873
          js_function->shared().is_compiled_scope(isolate));
874 875
      JSFunction::EnsureFeedbackVector(isolate, js_function,
                                       &is_compiled_scope);
876
    }
877

878
    if (!sfi->HasBytecodeArray()) continue;
879
    FixedArray constants = sfi->GetBytecodeArray(isolate).constant_pool();
880 881
    for (int i = 0; i < constants.length(); ++i) {
      if (!constants.get(i).IsSharedFunctionInfo()) continue;
882
      data = nullptr;
883
      if (!function_data_map.Lookup(SharedFunctionInfo::cast(constants.get(i)),
884
                                    &data)) {
885
        continue;
886
      }
887 888 889 890 891 892 893
      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;
894
      constants.set(i, *new_sfi);
895 896
    }
  }
897 898 899
  for (const auto& mapping : changed) {
    FunctionData* data = nullptr;
    if (!function_data_map.Lookup(new_script, mapping.second, &data)) continue;
900 901 902 903 904
    Handle<SharedFunctionInfo> new_sfi;
    // In most cases the new FunctionLiteral should also have an SFI, but there
    // are some exceptions. E.g the compiler doesn't create SFIs for
    // inner functions that are never referenced.
    if (!data->shared.ToHandle(&new_sfi)) continue;
905
    DCHECK_EQ(new_sfi->script(), *new_script);
906

907 908 909
    if (!function_data_map.Lookup(script, mapping.first, &data)) continue;
    Handle<SharedFunctionInfo> sfi;
    if (!data->shared.ToHandle(&sfi)) continue;
910

911 912 913 914
    isolate->debug()->DeoptimizeFunction(sfi);
    isolate->compilation_cache()->Remove(sfi);
    for (auto& js_function : data->js_functions) {
      js_function->set_shared(*new_sfi);
915
      js_function->set_code(js_function->shared().GetCode(), kReleaseStore);
916

917 918
      js_function->set_raw_feedback_cell(
          *isolate->factory()->many_closures_cell());
919
      if (!js_function->is_compiled()) continue;
920
      IsCompiledScope is_compiled_scope(
921
          js_function->shared().is_compiled_scope(isolate));
922 923
      JSFunction::EnsureFeedbackVector(isolate, js_function,
                                       &is_compiled_scope);
924
    }
925 926
  }
  SharedFunctionInfo::ScriptIterator it(isolate, *new_script);
927
  for (SharedFunctionInfo sfi = it.Next(); !sfi.is_null(); sfi = it.Next()) {
928
    if (!sfi.HasBytecodeArray()) continue;
929
    FixedArray constants = sfi.GetBytecodeArray(isolate).constant_pool();
930 931 932
    for (int i = 0; i < constants.length(); ++i) {
      if (!constants.get(i).IsSharedFunctionInfo()) continue;
      SharedFunctionInfo inner_sfi = SharedFunctionInfo::cast(constants.get(i));
933 934 935
      // See if there is a mapping from this function's start position to a
      // unchanged function's id.
      auto unchanged_it =
936
          start_position_to_unchanged_id.find(inner_sfi.StartPosition());
937 938 939 940
      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.
941
      SharedFunctionInfo old_unchanged_inner_sfi =
942
          SharedFunctionInfo::cast(new_script->shared_function_infos()
943
                                       .Get(unchanged_it->second)
944
                                       ->GetHeapObject());
945
      if (old_unchanged_inner_sfi == inner_sfi) continue;
946
      DCHECK_NE(old_unchanged_inner_sfi, inner_sfi);
947 948
      // Now some sanity checks. Make sure that the unchanged SFI has already
      // been processed and patched to be on the new script ...
949 950
      DCHECK_EQ(old_unchanged_inner_sfi.script(), *new_script);
      constants.set(i, old_unchanged_inner_sfi);
951 952 953 954
    }
  }
#ifdef DEBUG
  {
955 956 957
    // 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.
958
    DisallowGarbageCollection no_gc;
959

960
    SharedFunctionInfo::ScriptIterator script_it(isolate, *new_script);
961
    std::set<int> start_positions;
962 963
    for (SharedFunctionInfo sfi = script_it.Next(); !sfi.is_null();
         sfi = script_it.Next()) {
964
      DCHECK_EQ(sfi.script(), *new_script);
965
      DCHECK_EQ(sfi.function_literal_id(), script_it.CurrentIndex());
966 967
      // Don't check the start position of the top-level function, as it can
      // overlap with a function in the script.
968 969
      if (sfi.is_toplevel()) {
        DCHECK_EQ(start_positions.find(sfi.StartPosition()),
970
                  start_positions.end());
971
        start_positions.insert(sfi.StartPosition());
972
      }
973

974
      if (!sfi.HasBytecodeArray()) continue;
975 976 977
      // 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.
978
      FixedArray constants = sfi.GetBytecodeArray(isolate).constant_pool();
979 980
      for (int i = 0; i < constants.length(); ++i) {
        if (!constants.get(i).IsSharedFunctionInfo()) continue;
981
        SharedFunctionInfo inner_sfi =
982 983
            SharedFunctionInfo::cast(constants.get(i));
        DCHECK_EQ(inner_sfi.script(), *new_script);
984
        DCHECK_EQ(inner_sfi, new_script->shared_function_infos()
985
                                 .Get(inner_sfi.function_literal_id())
986 987 988
                                 ->GetHeapObject());
      }
    }
989
  }
990
#endif
991

992 993 994 995 996
  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);
997 998
}

999 1000
void LiveEdit::CompareStrings(Isolate* isolate, Handle<String> s1,
                              Handle<String> s2,
1001
                              std::vector<SourceChangeRange>* diffs) {
1002 1003
  s1 = String::Flatten(isolate, s1);
  s2 = String::Flatten(isolate, s2);
1004

1005 1006
  LineEndsWrapper line_ends1(isolate, s1);
  LineEndsWrapper line_ends2(isolate, s2);
1007 1008 1009

  LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
  TokenizingLineArrayCompareOutput output(isolate, line_ends1, line_ends2, s1,
1010
                                          s2, diffs);
1011 1012 1013 1014 1015 1016

  NarrowDownInput(&input, &output);

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

1017
int LiveEdit::TranslatePosition(const std::vector<SourceChangeRange>& diffs,
1018
                                int position) {
1019
  auto it = std::lower_bound(diffs.begin(), diffs.end(), position,
1020 1021 1022
                             [](const SourceChangeRange& change, int position) {
                               return change.end_position < position;
                             });
1023
  if (it != diffs.end() && position == it->end_position) {
1024 1025
    return it->new_end_position;
  }
1026 1027
  if (it == diffs.begin()) return position;
  DCHECK(it == diffs.end() || position <= it->start_position);
1028 1029 1030
  it = std::prev(it);
  return position + (it->new_end_position - it->end_position);
}
1031 1032
}  // namespace internal
}  // namespace v8